Закладка храма состоялась в июле 1865 г., строительство велось на пожертвования именитых горожан. Автор проекта – старший городовой архитектор Ф. Ф. Вагнер. Наблюдение за строительством осуществлял Э. И. Эзет. Главный престол церкви – в честь Воздвижения Честного и Животворящего Креста Господня – был освящён 4 октября (22 сентября по ст. ст.) 1870 г. Окончательно внутренняя отделка храма завершилась в начале 1900-х гг. В 1891 г. при церкви открылась школа для девочек, обучавшая в среднем 80 учениц. В годы советской власти церковь оставалась действующей, за исключением  1936-1943 гг. В 1990-е гг. храм был кафедральным собором Омско-Тарской епархии (до открытия Успенского собора в 2007 г.).

         Библиогр.: [Крестовоздвиженский кафедральный собор] // Знаменательные и памятные даты Омского Прииртышья, 2000. – Омск, 1999. – С. 57-58; Лебедева Н. И. Крестовоздвиженская церковь // Храмы и молитвенные дома Омского Прииртышья / Н. И. Лебедева. – Омск, 2003. – С. 24-26, 104-106, 154, 198-199: ил.; Лебедева Н. История омских храмов [Электронный ресурс]. – [Омск, 2009]. – Режим доступа: http: //www.omsktime.ru/church/krestovoz.html.