У подножия Крестовой горы вскоре после основания города Иркутска был поставлен крест, отметивший место будущей церкви. В 1717-1719 на горе возвели двухэтажную деревянную церковь. Каменную церковь, вместо древней, деревянной достроили к концу 1760 года. В 1779 на пожертвования купцов З. Щегорина и С. Удоровского приделали северный тёплый придел.

Изначально как деревянная, так и каменная церковь назывались Троице-Сергиевскими, но так как в городе имелась еще одна Троицкая церковь, то для удобства церковь на горе переименовали в Крестовоздвиженскую. В Советское время храм был закрыт, здесь размещался антирелигиозный музей. Удачное местоположение храма у пересечения главных улиц города на возвышенности обеспечивает цельное восприятие памятника среди старинных деревянных застроек. Даже сейчас храм остается одним из главных доминант в центре города.

В настоящее время является действующей, ведутся Богослужения.