В 1763 году командиром Сибирского корпуса был поставлен генерал-поручик Иван Иванович Шпрингер. Штаб корпуса находился в Омской крепости. Она к названному времени пришла в неудовлетворительное состояние: земляной вал сильно осел, ров почти до краев заполнился землей и мусором, тын заметно подгнил, казармы и другие внутри-крепостные постройки от той же гнили могли вот-вот рухнуть. Шпрингер решил поставить новую крепость, причем на правом берегу Оми, при ее слиянии с Иртышом. Для осуществления этой цели он пригласил инженеров-фортификаторов. Они направили в Петербург проект. В 1767 году он был утвержден. Весной 1768 года началась постройка новой Омской крепости. В связи с этим событием появились домыслы. Со временем они стали преданиями.

По старой Омской крепости и ее форштадтам пронеслась молва: императрица Екатерина Вторая намеревается побывать в Сибири и обязательно посетить Омск. Очень встревожился генерал Шпрингер: увидит императрица, как жалка крепость, плохо придется командиру Сибирского корпуса. Тут же он решил начать строительство новой Омской крепости. Данное предание имеет варианты. Один из них изложил Леонид Мартынов в книге "Крепость на Оми".

"Находились и такие злоязычные люди, которые утверждали, что Иван Иванович затеял всю эту постройку лишь для того, чтобы натянуть нос одному важному вельможе. Сей вельможа, князь Потемкин, мол, всяко удивлял матушку-государыню, когда она путешествовала на юг. А Иван Иванович приготовил государыне сюрприз здесь, на востоке. Прекрасная, как мираж, крепость возникнет над Иртышом навстречу царице. Это, мол, не Потемкинская деревня!"

Каторжник-мститель

Одной из построек новой Омской крепости был каторжный острог. Он находился в Степном бастионе, приблизительно на месте нынешнего медицинского училища, что у тыльной стороны драмтеатра.

Узники острога страдали не только от непосильной работы, которую выполняли в кандалах, но и от побоев, особенно от битья кнутом, и поэтому нередко совершали побеги. О смелости и дерзости некоторых беглецов среди жителей Омска того времени ходили легенды.

Из Омского каторжного острога бежал безвинно осужденный узник, по кличке Череда (череда - болотная трава, цветущая желтыми цветами – авт.). Вскоре после побега этого узника в Омске стали находить убитых офицеров и рядовых стражников, служивших в каторжном остроге и отличавшихся особой жестокостью по отношению к узникам. В правой руке каждого убитого оказывался пучок череды. Начальство острога, да и все горожане сразу догадались, кто и за что убивал. В остроге был создан специальный отряд для поимки бежавшего каторжника-мстителя. Много дней тот отряд впустую метался по городу и его окрестностям. За это время мститель уложил еще троих служивших в остроге истязателей. И вот отряд получил сведения, что Череда - в городе, на его южной окраине. Однако поимщики к месту, где укрывался Череда, примчались поздно: он ушел к югу от города. Началась погоня. Преследователи пересекли несколько березовых колков, пронеслись по нескольким перешейкам, разделявшим небольшие озерки, и оказались на берегу почти круглого озера в четверть версты шириной, где обнаружили шалаш, а на нем – травяную лежанку. От шалаша через заросли камыша вел к воде свежий след. Скорее всего, здесь был Череда. Однако самый тщательный осмотр окрестностей озера ничего не дал... С тех пор истязателей, служивших в Омском каторжном остроге, убитыми больше не находили.

И больше никто никогда ничего не слышал о каторжнике-мстителе по имени Череда. Возможно, он утонул в озере, а может быть, ушел в далекие от Омска места. А то озеро, расположенное приблизительно в семи верстах к югу от каторжного острога, стало называться озером Череды, позднее – Чередовым.