Строительство собора было инициировано в 1829 году по предложению временно исполняющего обязанности командующего Сибирским казачьим войском А. М. Лукина. Местом для возведения храма первоначально планировалась территория позади конно-артиллерийских казарм и конюшен. Однако император Николай I распорядился изменить расположение, указав на необходимость строительства церкви в центре города, между училищем и войсковой фабрикой. Закладка храма состоялась 15 мая 1833 года.
Архитектурный проект собора был разработан архитектором Василием Петровичем Стасовым, известным своими работами в Санкт-Петербурге и Москве. Впоследствии проект был доработан инженером А. А. Лещевым и архитектором П. И. Праманом. Храм возведён в стиле позднего классицизма с элементами ампира. Здание представляет собой крестово-купольную композицию с центральным куполом и колокольней. Внутреннее пространство включает три престола: главный — во имя Святителя Николая Чудотворца, правый — во имя Симеона Богоприимца и Анны Пророчицы, левый — во имя Великомученика Георгия Победоносца.
В июне 1840 года, ещё до завершения строительства, храм был освящён протоиереем Димитрием Пономарёвым. Официальное открытие и освящение главного престола состоялось 16 сентября 1843 года. .
В 1883 году собор приобрёл значимую реликвию — знамя Ермака с изображением святого Димитрия Солунского. Однако в 1918 году, в ходе Гражданской войны, оригинал был утрачён, и ныне в храме хранится его копия. В сентябре 1897 года при соборе была открыта четырёхклассная школа для девочек.
После Октябрьской революции 1917 года собор подвергся изменениям. В ноябре 1928 года здание было передано под культурные нужды, а в январе 1930 года официально закрыто для богослужений. Колокола, общий вес которых составлял 300 пудов, были сняты и отправлены на переплавку. Оставшееся церковное имущество поступило в Западно-Сибирский краевой музей.
В период с 1945 по 1965 годы в здании собора функционировал кинотеатр «Победа». С 1966 по 1970 годы помещение использовалось как склад оборудования городского сада и детская хоровая студия. В 1970 году здание было признано аварийным, и Омский горисполком принял решение о его сносе. Однако благодаря усилиям общественности и деятелей культуры решение было отменено. В 1974 году собор был признан памятником истории и архитектуры, и в середине 1970-х годов начались реставрационные работы. К 1983 году собор обрел свой первоначальный вид, и 12 июля 1983 года на храме были установлены кресты.
С декабря 1983 года до 1998 года в здании собора размещался Зал органной и камерной музыки Омской государственной филармонии. В 1998 году здание было передано Омско-Тарской епархии Русской Православной Церкви.
