Церковь во имя Николая чудотворца называется «кремлевскою» или «градскою» потому, что находится в древней кремле Владимира, в городе, «в тесном смысле этого слова», вблизи архиерейского дома у западной стены его. Время первоначального основания этой церкви нужно относить к глубокой древности, потому что еще в начале XVII ст. она известна под именем «Николы-Старого».
В описной книге Владимирского кремля-города 1626 г. значится «храм Николы чудотворца старого с приделами, с трапезою да теплый храм Симеона Столпника деревянные…». В патриарших книгах под 1628 г. также записано: «церковь великого чудотворца Николы старого…». Эти две деревянные церкви существовали до начала XVIII ст., но сведений о них сохранилось мало.
В 1710 г. при ней священниками были Федор Федоров и Андрей Федоров, диаконом сын его Алексей Андреев. В том же 1710 г. из патриаршего приказа был отпущен антиминс для освящения церкви Николы чудотв. в граде Владимире. Надо думать, что церковь была в это время перестроена, посему и потребовалось освятить ее вновь. Во время сильного пожара, бывшего во Владимире 1 октября 1719 г., Николо-Кремлевская церковь сгорела вместе с теплой церковью.
В 1721 г. прихожанами приобретена была в селе Погребищах теплая церковь во имя Пресвятой Богородицы Владимирской и из нее во Владимире построена была в том же году также теплая церковь, потому что холодная церковь во имя Николая чудотв. построена только в 1747 г., как это видно из Топографического описания г. Владимира 1761 г. Недостаток средств, вероятно, был причиною того, что холодная церковь слишком двадцать лет после пожара не была построена.
В 1761 г. вместо этих старых церквей начата была постройкою несколько на ином месте каменная церковь с приделом. Придел был окончен постройкою в 1762 г. и в этом же году с благословения преосвящ. Антония, епископа Владимирского и Ярополчского, был освящен во имя Симеона Столпника. Никольский же храм окончен постройкою только в 1769 г.
До 1850 г. Никольская церковь сохраняла свой первоначальный вид. В этом году с южной стороны пристроен новый придел, так что в настоящее время в церкви три престола: в холодной – во имя св. Николая чудотв., в теплом правом приделе – во имя Симеона Столпника, а в левом – в честь Тихвинской иконы Божий Матери. В связи с церковью и одновременно с ней выстроена достаточно высокая каменная колокольня.
Церковные документы хранятся в целости: копии метрических книг с 1803 г., исповедные росписи с 1829 г. Церкви принадлежит капитал 225 руб., процентами с коего пользуется, и небольшая лавочка, помещающаяся в церковной сторожке; деньги, получающиеся от сдачи в аренду лавочки, идут в пользу церкви. Причта по штату положено: священник и псаломщик. Содержание его составляют: доходы от служб и треб, проценты с капитала 4396 руб. 56 коп., положенного на вечное поминовение разных лиц, и арендная плата за огородную и сенокосную церковную землю. Церковных домов для причта нет. В приходе Николо-Кремлевской церкви по клировым ведомостям числится 290 душ муж. пола и 330 жен.; все живут в г. Владимире. С 1876 г. при церкви открыто церковно-приходское попечительство.
В.Г. Добронравов, В.Д. Березин «Историко-статистическое описание церквей и приходов Владимирской епархии» выпуск 1. Губ. гор. Владимир, Типо-Литография В.А. Паркова, 1893 г.