В декабре 1913 года было принято решение о строительстве храма, за что город обязан недавно назначенному епископу Омскому и Павлодарскому Андронику (Владимиру Никольскому). Он привнес в местную епархию традиции Великого Новгорода и списки с чудотворных икон, включая копию Новгородской иконы Знамения Царицы Небесной, которая сначала хранилась в его домовой церкви.

Участок для храма нашли в феврале 1914 года, после чего начался сбор средств. В строительный комитет входил сам Андроник, а работы велись под руководством подрядчика И.П. Окиншева. Планировалось, что в здании разместятся не только церковь, но и помещения для школы и миссионерской деятельности. Строительство завершали уже без Андроника, так как летом того же года его назначили епископом Пермским и Кунгурским, где в 1918 году он стал архиепископом незадолго до казни.

Строительство храма замедлилось из-за Первой мировой войны и последующей гражданской войны, но в 1918 году храм все же освятили. Первым протоиереем стал Василий (Пляскин). Одноэтажное здание из красного кирпича, вытянутое с запада на восток, завершалось трехчастной апсидой. Притвор был узким, но под зданием находился вместительный подвал. Декор выполнен в стилизованной русской манере. Первая шатровая колокольня стояла рядом с храмом, но в 1923 году ее разобрали и поставили новую над притвором.

Храм пережил первые годы Советской власти, но был закрыт в 1938 году, а здание использовали для городских нужд. Церковные ценности изъяли, часть отправили в Москву, часть передали в местные дома культуры, а более 100 ценных икон сожгли. В храме находились ценности закрытых церквей, поэтому среди уничтоженного было много старых икон.

В 40-е годы в здании бывшей церкви разместилась шиномонтажная мастерская, для которой купола и колокольня оказались лишними. Позже здесь была автошкола. Здание вернули Омско-Тарской епархии в начале 90-х годов. Тогда же его включили в местный реестр охраняемых памятников архитектуры и начали восстановление храма. Луковичная главка и шатер над апсидой появились в 1999 году по проекту архитектора П.А. Самосудова. Сейчас церковь действует, при ней работает школа ремесел. Она расположена на улице Куйбышева, рядом с пересечением с улицей Маяковского. До Знаменской церкви можно добраться любым транспортом до остановки «ул. Степная».