В 1872 г. старанием артиллерийского подполковника Н.А. Герасимова при помощи военного штаба и частных жертвователей был построен деревянный Александро-Невский храм в г. Зайсан, приход которого в конце XIX – начале XX вв. входил в состав благочиния Усть-Каменогорских городских и уездных церквей, возглавлявшегося протоиереем Александром Владимировичем Дагаевым (священномученик). Приходской штат состоял из священника Геннадия Стефановича Коченгина и псаломщика Н.М. Щепетильникова. Позднее псаломщиком был Александр Бедарев.
Геннадий Стефанович преподавал в учебных заведениях города Закон Божий. Отец Геннадий Коченгин был дружен с родителями выдающегося русского поэта Павла Васильева Николаем Корниловичем и Глафирой Матфеевной Васильевыми, с 1906 г. проживавшими в Зайсане. Николай Корнилович являлся заведующим Зайсанским мужским приходским училищем. В метрической книге Александро-Невской церкви сохранилась запись от 23 декабря 1909 г. о рождении Павла Николаевича Васильева.
В историко-краеведческом музее г. Зайсан хранится надгробная плита с могилы малолетнего сына зайсанского священника Дуплева. Несомненно, данный священник служил в Александро-Невской церкви, поскольку даты надгробия относятся к концу XIX вв., а второй городской храм – Никольский военный собор - был построен только в 1905 г. В этом же музее хранятся церковные колокола, однако их изначальная принадлежность не выяснена и лишь с определённой долей условности можно отнести их к утвари Александро-Невской церкви.
Документы, хранящиеся в Центре документации новейшей истории Восточного Казахстана г. Семипалатинска, свидетельствуют о том, что в 1923 г. община Александро-Невской церкви г. Зайсана была обновленческой «стоящей на платформе Священного Синода Российской Православной Церкви». Имеется опись утвари церкви, списки верующих и церковных активистов, а также отдельные разрозненные документы, носящие характер переписки с власть предержащими советскими органами. Почти сразу после установления Советской власти второй зайсанский храм – Никольский собор, находящийся на территории военного городка, был закрыт и Александро-Невская церковь оставалась единственной действующей в городе. К концу 1930-х гг. храм был закрыт и впоследствии разрушен (другая версия – сгорел или намеренно сожжён).
В 2001 г. на средства предпринимателя Дудника был построен из белого силикатного кирпича небольшой храм, освященный в честь Благоверного князя Александра Невского. На месте прежнего утраченного деревянного храма теперь расположена частная усадьба, поэтому новый храм возводился на другом месте, даже не на исторической территории города, а в заречной его части, когда-то бывшей казачьей станицей. Остатки немногочисленного русского населения сосредоточены преимущественно в этом районе. В 2007 г. русских насчитывалось в целом в районе не более 850 человек, ныне ситуация ещё более плачевная, наблюдается явная тенденция к полному исчезновению русского присутствия в регионе.
В течение нескольких лет в Зайсане постоянно проживал священник Николай Давыдов, но вследствие резкого сокращения пасомых и образования вакансии в приходе Зыряновска был переведён настоятелем Князе-Даниловского храма этого города, где русские составляют подавляющее большинство населения. В данное время община Александро-Невского храма окормляется клириками Усть-Каменогорского благочиннического округа.
Б.Г. Герасимов. Старинные церкви Семипалатинской области. // Б.Г. Герасимов. Избранные труды: факсимильное издание. Усть-Каменогорск, Шыгыс-Баспа, 2000; Адрес-календарь Семипалатинской области. – Семипалатинск, 1914 г.