Еще в XIX веке на месте Никольской церкви существовала деревянная часовня и небольшая старообрядческая моленная при ней. По одной из версий, она появилась в 1815 году на средства купца Н.Д. Царского, благодаря которому получила неофициальное название «Царской моленной». Позднее участок перешел к Рахмановым, и община, сформировавшая вокруг моленной, стала именоваться «рахмановской». В 1870-х годах у часовни появился престол, она была преобразована в храм, окончательно оформившийся после 1905 года, когда старообрядцам разрешили легально строить свои церкви.

Проект нового храма на Тверской заставе, созданный архитектором И.Г. Кондратенко, был утвержден еще в 1908 году, но приступить к его реализации в то время не удалось. В последний раз в старом здании служили 16 марта 1914 года, после чего его разобрали, а на его месте начали возводить новую церковь во имя святого Николая Чудотворца, уже по проекту архитектора А.М. Гуржиенко.

Храм создан в неорусской стилистике, ориентирующейся на новгородское храмовое зодчество. Одноглавый, с тремя закомарами с каждой стороны, укрепленный контрфорсами и прорезанный длинными щелевидными окнами, он должен был напоминать церковь Спаса на Нередице в Великом Новгороде. К храму пристроена шатровая колокольня, в основании которой существовал придел во имя Илии Пророка. Фасады украшены кирпичным декором, характерным для северной архитектуры.

Первая мировая война замедлила, но не остановила строительство, средства на него жертвовали известные старообрядцы: С.Т. Морозов, Е.В. Шерупенкова, П.В. Иванов, А.Е. Русаков. Завершенный вчерне в 1915 году, храм был освящен только в 1921, когда завершилась отделка интерьеров. Богослужения в церкви прекратились в 1940–41 годах, но до начала Великой Отечественной войны в ее подвале была моленная адвентистов седьмого дня – протестантского течения, не относившегося к старообрядчеству. Внутри в военное время разместился склад московской противовоздушной обороны, а после – скульптурная мастерская Министерства культуры СССР. Есть версия, что здесь скульптор С.М. Орлов трудился над созданием памятника Юрию Долгорукому. Убранство и планировка здания были полностью изменены изнутри, храм лишился главы и шатра колокольни.

Первый молебен в приделе Ильи Пророка состоялся в 1995 году, с этого времени начался процесс передачи здания старообрядческой общине и его реставрации. В 2000-х годах историческая застройка рядом с храмом была уничтожена и ее место заняли многоэтажные здания новой архитектуры. Церковь получила новый, диссонирующий фон.