Церковь устроена в 1993 г., размещена в перестроенном кирпичном здании бывшего кинотеатра "Луч". Над центром здания надстроена деревянная шатровая звонница. Освящён храм 31 декабря 1993 г. Приход во имя Всех Святых был первым православным приходом на левом берегу города.
6 октября 1999 г. по ходатайству Преосвященного Сергия, епископа Новосибирского и Бердского (Соколова), и по благословению Патриарха Московского и всея Руси Алексия II, решением Священного Синода (журнал № 106) приход во имя Всех Святых преобразован в монастырь святых Новомучеников Российских. Община приобрела официальный статус. Так был организован первый монастырь в черте города Новосибирска.
Жилой корпус монастыря находится в бывшем клубе, переданном Новосибирским оловянным комбинатом. В монастыре есть домовый храм, освящённый в честь преподобного Серафима Саровского Чудотворца. Собрана большая библиотека духовной литературы, а также аудио-видеотека. 20 ноября 2006 г. в храме во имя Всех Святых была окончена установка самой большой в мире иконы «Всех Святых». Она расположена на потолке храма.
С 1998 г. строительные работы по возведению храма честь святых Новомучеников Российских возобновились. Строится монастырский комплекс и духовное учебное заведение. В апреле 2003 г. был поднят купол, освящённый архиепископом Новосибирским и Бердским Тихоном.
Храм в честь святых Новомучеников Российских был освящен 25 июня 2005 г. Высокопреосвященным Тихоном, архиепископом Новосибирским и Бердским, в сослужении священников Новосибирской епархии. С этого дня храм открыт для посещения.
На улице Сибиряков-Гвардейцев построена часовня-памятник в честь Владимирской иконы Божией Матери, посвящённая памяти воинов, погибших во время Отечественной войны и всех пострадавших за Веру и Отечество в годы гонений и репрессий. В часовне в дни Великих праздников священнослужители монастыря совершают молебны. По благословению Владыки Тихона организовано подворье монастыря в р.п. Венгерово и г. Купино Новосибирской области, где ведётся натуральное хозяйство для снабжения монастыря.
Священнослужители монастыря окормляют осужденных в местах лишения свободы (УФ91/2 и УФ91/18). В 18-й колонии построен храм-часовня в честь Владимирской иконы Божией Матери. Иконостас, престол, жертвенник и другая церковная утварь изготовлена руками осужденных. В УФ91/2 тоже имеется помещение, в котором расположена часовня во имя преподобного Сергия Радонежского.
http://www.orthedu.ru/nskeparh/eparhia/c-gor-okrug/vseh_sv.htm ; http://www.liveinternet.ru/users/4624630/post382340856/