В 1711–1715 годах деревянный Никольский храм был заменен каменным. Он состоял из двухсветного четверика с трехчастной апсидой и небольшой трапезной. Крестообразная церковь имела низкую трапезную и небольшую отдельно стоявшую колокольню. Новый храм был построен на пожертвования почетного гражданина А. И. Малюшина и московских купцов М. Я. Заботина, И. Я. Львова. На средства жертвователей в Никольской церкви установили великолепный иконостас, иконы которого были украшены ризами тонкой работы. Храм был освящен 16 мая 1715 года преосвященным Иоанникием Ставропольским. При храме устроили бесплатную столовую для бедных, богадельню и мастерские. В 1722 году по желанию благотворителей в церкви Святителя Николая устроили придел во имя преподобного Сергия Радонежского.
В 1791 году храм Святителя Николая в Дербеневе был отделан заново: появился новый иконостас, обновлена лепнина. При церкви возвели красивую двухъярусную колокольню со сферическим куполом. Второй ярус колокольни сделали в виде изящной ротонды. В это же время появилась каменная ограда. Нашествие французов в 1812 году чудесным образом не коснулось Никольского храма. В московском пожаре, испепелившем город со многими его святынями, церковь практически не пострадала. В первой половине XIX века в начале Уланского переулка жила в деревянном доме тетка А. С. Пушкина, Елизавета Львовна Сонцова. Пушкин приезжал к своей родственнице в мае 1830 года. В письмах к отцу Пушкин неоднократно передавал поклоны «тетушке и ее семейству». Елизавета Львовна называла поэта не иначе как «мой племянник, несчастная жертва». А в середине XIX века в приходе церкви жил дядя Д. И. Менделеева, Василий Дмитриевич Корнильев, у которого мальчиком останавливался будущий создатель Периодической системы химических элементов.
В 1878 году по проекту знаменитого архитектора К. М. Быковского к храму святителя Николая в Дербеневе пристраивается придел во имя иконы Божией Матери «Всех скорбящих Радость». Эта икона появилась в XVII веке и стала одним из главных московских чудотворных образов. Во многих храмах Москвы приделы освящались в честь Скорбященской иконы. На ней изображена Богоматерь, состоящая в мандорле (сиянии), окруженная страждущими и больными людьми и ангелами, несущими добродетели. Название «Всех скорбящих Радость» восходит к строке одной из Богородичных стихир. В 1895 году тот же Быковский перестроил левый Сергиевский придел. Благодаря перестройке церковь приобрела новое градостроительное значение и стала архитектурной доминантой, видной с обеих частей изогнутого Уланова переулка. Изменилось композиционное решение Никольского храма. У него появилась высокая главка, установленная над декоративной аркой лицевой стены, максимально приближенной к линии переулка. Основной объем церкви был увенчан стройным восьмериком, что придало ей вид, характерный для церковной архитектуры XVIII века.