Уже через год после своего возникновения в 1854 году Верненская крепость стала прирастать станичным поселением. В 1858 году на Станичной площади была воздвигнута небольшая церковь, которую первый настоятель Евтихий Вышеславский освятил в честь великомучениц Веры, Надежды, Любови и матери их Софии.
В своем первозданном виде церковь просуществовала до 1871 года. К этому времени население Верного значительно увеличилось.
В 1870 году здание храма было перенесено в Мало-Алматинскую станицу, а на его месте начато строительство храма из обожженого кирпича. 23 декабря 1871 года храм был освящен под тем же именем.

Еще 1867 году укрепление Верный преобразовано в административный центр Семиречинской области. Тогда же Туркестанский генерал-губернатор ходатайствовал об учреждении в крае самостоятельной архиерейской кафедры. Назначенный на кафедру с титулом «Туркестанский и Ташкентский» архиерей, высокообразованный и многоопытный Архиепископ Софония (Сокольский), в 1873 г. обратил Софийский храм в кафедральный собор.

28 мая 1887 года, во время Первого Алма-атинского землетрясения, собор был полностью разрушен. Нa площади близ храма похоронены в братской могиле около 300 жителей Больше-Алмаатинской станицы, погибших в результате землетрясения.

Исследование конструкций уцелевших зданий, их сопоставление с утраченными домами показало, что каменные постройки пострадали значительно сильнее деревянных. В 1893 году на месте разрушенного храма был заложен новый, из тянь-шаньской ели по проекту архитектора Вячеслава Николаевича Брусенцова.
Новый храм был закончен в 1895 году. В южной его части располагается некрополь, в котором покоятся останки первых верненских епископов Софонии Сокольского и Никона Богоявленского.
К тому времени городские власти приняли решение строить кафедральный собор в другой части города (Вознесенский собор). Софийский храм перестал быть кафедральным.

Очередное испытание постигло Софийский собор в декабре 1910 года, когда Верный подвергся страшному и разрушительному землетрясению. После была революция 1917 года, затем захват обновленцами в 20-х годах. В 1929 и 1931 годах власти предпринимали попытки закрыть собор и сделали это окончательно в 1937 году. Обновленческое духовенство храма было арестовано и расстреляно.
После закрытия здание храма переоборудовали в клуб Красных Партизан, потом в кинотеатр «Ударник», затем в его стенах размещался кукольный театр. В конце 80-х годов прошлого столетия оно пришло в аварийное состояни, чему способствовали местные жители, растаскивавшие здание.
Чтобы спасти бывший собор от полного разрушения, Министерство культуры КазССР вынуждено было ввести должность сторожа, чтобы сохранить до начала реставрации здание, входившее в список охраняемых памятников культуры и архитектуры. В условиях политического и экономического кризиса на рубеже 1980-х и 1990-х годов дело не только не дошло до реставрации, но здание было выведено из реестра памятников, должность сторожа упразднили

В 1989 году епархия предприняла попытку вернуть Софийский храм Церкви. Вопрос о возвращении собора обсуждался и в местной прессе. Но, едва об этом заговорили, он был окончательно разрушен.

Решение о возрождении Софийского собора было принято Митрополитом Мефодием в 2003 году, когда он возглавил Астанайскую и Алматинскую кафедру.
19 мая 2004 года Митрополит Мефодий освятил место возведения Софийского собора.
21 ноября 2005 года, в день празднования Собора архистратига Михаила, владыка Мефодий совершил чин освящения надгробного креста над могилами святителей Туркестанской кафедры архиепископа Софония († 1877) и епископа Никона († 1897). 19 мая 2004 года останки святителей были торжественно перезахоронены в нововыстроенном склепе, расположенном неподалеку от фундамента разрушенного собора.

25 апреля 2006 года были освящены отлитые для храма колокола. Их общий вес – более трех тонн. Самый крупный весит 1600 килограммов и является самым большим колоколом в Казахстане.

12 июня 2006 года освящены и установлены купола и кресты. 30 сентября 2007 года Митрополит Мефодий в сослужении алматинского духовенства, при большем стечении богомольцев освятил возрожденный храм.
Возрожденный собор – точная копия старого. Единственное его отличие в том, что он теперь не из дерева, а из современных сейсмостойких материалов.

Важными событиями в жизни прихода являются престольные праздники храма: день памяти святой блаженной старицы Матроны 19 апреля – 2 мая и день памяти святых мучениц Веры, Надежды, Любови и матери их Софии 17 –30 сентября.