Храм находится в центре Таганской слободы, возникшей в местности, издревле носившей название «Болвановка». Некоторые исследователи связывают происхождение названия с «болваном» — идолом, татарским либо языческим, который мог находиться в тех местах, другие считают, что название связано с поселением там мастеров, изготавливающих болванки для производства шляп. Первый храм на месте современного являлся приходским храмом ремесленников. Существует предположение, что первый, деревянный храм был построен в 1506 году, однако он не упоминается до 1632 года. Доподлинно не известно, когда именно началось строительство каменного храма, так, одна из версий гласит, что по благословению патриарха Иоакима в 1682 году был начат сбор средств среди прихожан на постройку нового храма, однако нужную сумму удалось собрать только к 1697 году. Другая версия сводится к тому, что деньги всё же удалось собрать, и в 1682 году была выстроена маленькая каменная церковь с шатровойколокольней, а в начале XVIII века она была перестроена по заказу князей Гагариных.
Каменный храм, сохранившийся до наших дней, был построен под руководством московского зодчего Осипа Старцева. Старцев выступил как весьма консервативный архитектор (предполагают, что его консерватизм был обусловлен несогласием с петровскими реформами), и церковь была выстроена им в традиционном московском стиле — так называемом «московском барокко», однако более архаичном, чем предыдущие его постройки. Церковь Николы на Болвановке иногда называют последней средневековой постройкой старой Москвы.
Впоследствии церковь сильно пострадала во время пожара в середине XVIII века, в частности, был практически полностью утрачен первоначальный белокаменный декор. Он неоднократно восстанавливался и поновлялся на средства прихожан. В 1875—1876 годах церковь была перестроена по проекту архитектора Василия Карнеева, а в 1900—1905 годах на средства М. В. Коликова под руководством архитектора В. А. Осипова была проведена масштабная реставрация, частично вернувшая храму первоначальный облик. Были возвращены некоторые архитектурные детали. Росписи были поновлены художниками И. М. и М. И. Дикаревыми.
Около 1920 года храм был закрыт, разорён и осквернён. В 1944 году, при строительстве станции метро «Таганская» и перестройки Таганской площади была предпринята попытка разрушить храм, были уничтожены главы и верхушка колокольни, но от окончательного уничтожения его спасло присвоение статуса памятника архитектуры. Впоследствии храм был восстановлен, не вернули только кресты на куполах.
