Место для постройки храма было выбрано в 1912 г. первым епископом Верненским и Семиреченским Иннокентием (Пустынским), обратившимся к населению с призывом на народные пожертвования выстроить церковь. Ставил храм епархиальный архитектор А. П. Пугаченко. Первое богослужение в новом храме было совершено осенью 1915 г. Епископ Иннокентий освятил церковь в честь иконы Божией Матери «Всех скорбящих Радость». Первыми священниками были: о. Сергий Бредников, о. Иаков Якушев и о. Андрей Дольников. В июне 1933 г. церковь была закрыта и разорена, духовенство арестовано. Здание храма стало использоваться не по назначению: с 1933 г. здесь располагался пункт местного НКВД, с 1937 г. — клуб «Красный текстильщик», с 1949 г. — пошивочная мастерская, с 1959 г. — кинотеатр, затем — склад хим. продукции. С 1962 г. церковь пустовала. В 1973 г. в ней был размещен филиал городской библиотеки, который занимал только половину здания, а остальная часть его пустовала . Капитальный ремонт церкви не проводился на протяжении последних 10-15 лет, в результате чего она находилась на грани разрушения.
В 1995 г. верующие г. Алматы обратились к правящему архиерею с просьбой походатайствовать перед городскими властями о возвращении здания в ведение епархии. В 1997 г. храм был передан Церкви в бессрочное и безвозмездное пользование. Здание находилось в аварийном состоянии: основания не было, фундамент был полностью разрушен. Первые восстановительные работы по храму проводились под руководством назначенного настоятеля иерея Игоря Светличного и эконома Г. Г. Беленок.
В июле 1998 г. решением Акима города здание храма внесено в государственный список памятников истории и культуры г. Алматы местного значения. 6 ноября 1998 г. в Престольный праздник был отслужен первый молебен. В 1999 г. настоятелем храма был назначен прот. Евгений Воробьев (до настоящего времени). Начались работы по капитальному строительству и реконструкции здания. Заменен фундамент, храм обозначился центральным купольным навершием, пристроена колокольня. Подняты колокола, предоставленные в дар настоятелем Казанского собора г. Алматы. Храм всегда открыт для верующих. Богослужения проводятся в воскресные и праздничные дни. Каждую среду совершается молебственное пение Божией Матери с чтением акафиста перед чтимой иконой.
Храм построен в традиционном православном стиле в виде креста. Однокупольный. Размеры — 27х16 м. Деревянный. В настоящее время под всем зданием бутовый фундамент заменен на бетонный. Пристроена колокольня. Храм обложен облицовочным кирпичом.
