Решение о возведении церкви было принято 29 октября 1878 года на общественном сходе жителей Колывани. Первоначально предполагалось, что церковь будет носить имя Покрова Пресвятой Богородицы. Однако после убийства 1 марта 1881 года императора Александра II колыванский купец II гильдии Кирилл Климович Кривцов «пожелал на свои средства построить в память убиенного Александра II церковь имени Александра Невского по плану, утвержденному для церкви Покрова» и получил разрешение императора Александра III. Будучи купцом II гильдии и очень богатым человеком, Кирилл Климович Кривцов (умер в 1887 году) активно занимался благотворительностью, был видным меценатом и общественным деятелем, награждался золотой медалью на Станиславской ленте «за заслуги по духовному ведомству», избирался гласным в городскую думу. С его именем связано строительство двух приделов к собору Святой Живоначальной Троицы.
Грамота от Томской духовной консистории с благословением на заложение церкви Александра Невского была подписана в «лето от Рождества Христова тысяча восемьсот восемьдесят первое, Октября в седьмой день». После окончания строительства церковь была освящена 4 декабря 1887 года преосвященнейшим Исаакием, епископом Томским и Семипалатинским.
Церковь стала вторым православным храмом в городе Колывани. Она отапливалась пятью голландскими печами, имела иконостас «длиною 10,5 аршин и высотою 13 аршин», оцененный в 3 000 р., была обнесена кованой металлической оградой. При церкви в 1890 году колыванским купцом II гильдии Евграфом Александровичем Жернаковым была построена церковноприходская одноклассная школа.
В советское время, несмотря на массированную антирелигиозную пропаганду, службы в церкви продолжались до начала 1960-х годов. Тем не менее, в 1962 году церковь была закрыта, а в 1968 году, по решению руководителей райкома и райисполкома, – снесены купола. Позднее были утрачены дверные полотна и рамы оконных проемов, пол, деревянные хоры, лестницы на хоры и колокольню, убранство интерьера и ограда церкви.
История возрождения церкви была очень долгой. Началась она 19 мая 1973 года, когда кандидат архитектуры, доцент Новосибирского инженерно-строительного института Н.И. Болотин, инспектор управления культуры Б.П. Шипилов и архитектор В.Ф. Болдырев составили акт обследования церкви и подняли вопрос о ее восстановлении. Тремя годами позже было принято решение Новосибирского
облисполкома о постановке здания церкви на госохрану. В начале 1980-х годов мастерская специального научно-реставрационного хозрасчетного производственного учреждения «Новосибирскреставрация» приступила к выполнению первых проектных работ по реставрации церкви и приспособлению ее под музей крестьянских ремесел и техники. В 1987 году архитекторами Н.Н. Тюковой, С.Н. Богомазовой, Е.А. Слепчук были выполнены подробные обмерные чертежи церкви, а в 1988 году составлена смета на первоочередные ремонтно-реставрационные работы С 1990 года на средства Новосибирской епархии в церкви начали проводиться восстановительные работы. В мае 1992 года в Колывани побывал Святейший патриарх Московский и всея Руси Алексий II, который освятил камень, заложенный под фундамент нового женского монастыря на территории церкви. С 19 июля 1992 года в храме снова стали проходить службы.
Церковь во имя святого Александра Невского расположена в южной части Колывани на территории женского Покровского монастыря, огороженного построенным в 1990-х годах кирпичным забором. Участок территории занимает квартал регулярного плана и расположен в границах улиц Калинина, Горького, Ольги Жилиной и Пролетарской. Церковь хорошо обозревается издалека, с автодорожной трассы, со стороны пониженных рек Чаус и Оёш, выделяясь своими значительными раз-мерами, силуэтом и светлой окраской на южном склоне плоского плато.
С северо-западной стороны, в 70 м от церкви, расположена братская могила жертв Колыванского восстания 1920 года – памятник истории, находящийся на государственной охране.
Архитектура церкви отличается простотой и цельностью композиции, стройностью силуэта, хорошими пропорциями объемов и деталей. Двуглавая церковь принадлежит к типу традиционных трапезных церквей с трехчастным членением плана (тип церкви «кораблем»), когда на одной композиционной оси восток–запад находятся основной объем, трапезная и колокольня. Храм бесстолпный, одноапсидный. Структура храма симметричная, осевая.
Основной объем, высотой в два яруса, восьмигранный в плане, перекрыт сомкнутым восьмилотковым сводом со световым восьмериком – барабаном. Барабан освещен четырьмя вытянутыми арочными оконными проемами. Стены основного объема имеют разную ширину – большую по граням, обращенным на север, юг, запад, восток. Все грани основного объема прорезаны арочными высокими оконными проемами: строенными с южной и северной сторон и одиночными, выходящими на юго-запад, юго-восток, северо-запад и северо-восток. Грани стен основного объема имеют полукруглые закомары с небольшими килевидными завершениями. Решение соединения сомкнутого свода основного объема с цилиндрическими сводами по закомарам является отличительной конструктивной особенностью храма, не свойственной другим сибирским храмам. Световой барабан над храмом увенчан восьмигранным куполом луковичной формы. С востока к основному объему примыкает полукруглая алтарная апсида, перекрытая конхой с миниатюрной луковичной главкой. Объемы входов в церковь с севера и юга выполнены высотой в один этаж, перекрыты цилиндрическими сводами. Арочные порталы входов с килевидными завершениями повторяют рисунок закомар. Квадратный в плане объем трапезной, высотой несколько ниже основного объема, перекрыт цилиндрическим сводом, имеет с севера и юга по два высоких арочных оконных проема.
Колокольня церкви трехъярусная. Нижний объем, притвор – четверик, перекрытый цилиндрическими сводами и завершенный закомарами. Два верхних яруса колокольни – восьмерики. Второй ярус имеет глухие стены, третий ярус звона открыт четырьмя арочными проемами по сторонам света. Колокольня увенчана восьмигранным куполом луковичной формы. Со стороны западного фасада к притвору примыкает входной тамбур – паперть. В паперти повторяется архитектурное решение северного и южного входов – перекрытие цилиндрическим сводом, килевидное завершение арочного входного портала.
Фасады декорированы ступенчатыми пилястрами с раскрепованными карнизами, ширинками, ложными окнами. Горизонтальные профилированные карнизы разделяют фасады на ярусы по высоте. Вертикали стен поддержаны вертикалями пилястр, вытянутых окон. Полукружия сводов имеют соответствия в полукружиях закомар, порталов, арочных окон. В верхней части стен притвора расположены круглые ниши-киоты. Убранство фасадов дополняет бело-голубая окраска стен, золоченые купола и кресты на главках.
Стены церкви сложены из красного кирпича, оштукатурены. Фундаменты бутовые, цоколь облицован известняком. Кладка стен выполнена на известковом растворе. Покрытия – кирпичные своды. Кровли металлические, устроены по деревянным стропилам и обрешетке. Ступени крылец – из гранитных блоков.
Основные габариты в плане: 24×44 м, высота колокольни 27 м.
Общее композиционное построение, пластика и декор фасадов церкви позволяют отнести здание к примерам эклектики, где традиции классицизма второй половины XIX века дополнены стилизацией в формах византийского и древнерусского зодчества.
Категория охраны: Памятник архитектуры регионального значения, Постановление главы администрации Новосибирской области от 14.04.1976 г. № 236.
Церковное краеведение. Энциклопедия Колыванского района. «Памятники истории, архитектуры и монументального искусства Новосибирской области. Книга 2. Районы и города Новосибирской области (памятники, состоящие на государственной охране): Каталог». - 2-е изд., перераб.- Новосибирск, 2012 г.