В документах XVIII века эта церковь называлась Николаевской «что за земленым валом» или «что за земленым городом», иногда «что в Пальцевой слободе», по фамилии купцов Пальцовых. В середине XIX века для отличия от других храмов во имя Николая Чудотворца, имевшихся в Туле, осталось уточнение «что за валом», хотя сам вал, проходивший примерно по нечетной стороне нынешней улицы Советской, прекратил свое существование в конце XVIII века. Это же название дошло до наших дней. По некоторым данным, деревянный храм появился на этом месте в 1600 году. Возведение каменного двухэтажного здания началось в 1703 году. К 1705 году построили нижнюю церковь во имя Николая архиепископа Мирликийского Чудотворца, а к 1712 году верхнюю во имя Владимирской иконы Божией Матери. Храмовый образ Пресвятой Богородицы и другие образа иконостаса были списаны с икон Успенского собора Московского кремля и других древних московских икон. Верхний храм был холодный, а нижний теплый. Церковь после этого называли как Николозавальской, так и Владимирской.
Основные вклады на строительство каменного здания храма внесли Симеон Яковлевич Губин, а также Пальцовы, Дружинины, Ксенофонтовы, Сабинины. В 1770 году к нижней церкви слева пристроили придел во имя преподобного Нила Столбенского. В 1826 году его перенесли на правую сторону, а с левой стороны устроили в 1835 году придел во имя архидиакона Стефана. В 1831 году на правой стороне верхней церкви устроили придел во имя Кирика и Иулиты. В 1832 году в верхнем храме появился придел во имя новоявленного чудотворца святителя Митрофана Воронежского. В особом киоте этого придела хранилась часть нетленного омофора святителя, обретенная вместе с его мощами. Придел был устроен купцом М. И. Федуркиным. Каменная колокольня построена в 1833 году иждивением Ивана и Александра Татариновых. На ней было семь колоколов, самый большой из которых весом в 100 пудов был отлит в Москве в 1794 году. 1 апреля 1800 года храм пострадал от наводнения, вода залила нижнюю церковь, стронулась с места престол в приделе Нила Столбенского, были и другие повреждения. Церковь и в последующее время не раз подвергалась наводнениям, хотя и без таких последствий. В 1851—1856 годы при Николозавальской церкви старанием церковного старосты мещанина Евфимия Неглинского был построен двухэтажный каменный дом с двухэтажным каменным флигелем вместо существовавшей до тех пор одноэтажной богадельни, известной с 1782 года. На нижнем этаже дома разместилась богадельня, а его верхний этаж и флигель сдавались внаём. Вырученные деньги шли на содержание храма и проживавших в богадельне нищих. Богадельня была рассчитана на проживание 20 человек обоего пола. Вначале она предназначалась для бедных бесприютных людей. Но в 1862 году Николозавальская богадельня была признана самой удобной для помещения бедных духовного звания. В 1895 году при храме была открыта церковноприходская школа. На плане Тулы 1891 года улица, на которой стоял храм, именуется по одному из его названий, Владимирской. На плане города 1908 года эта же улица именуется по второму названию храма, Николозавальской. В 1927 году улица Николо-Завальская была переименована в улицу Войкова. Николозавальская церковь была закрыта согласно постановлению президиума Тульского губисполкома от 19 февраля 1924 года.
Из документа следует, что храм был опечатан за год до его официального закрытия. Впрочем, немного позже городские власти вознамерились разобрать здание храма. Это не осуществилось только потому, что в бывшую церковь свезли огромный массив документов ликвидированных учреждений, и эти документы больше негде было хранить. С 1926 года в здании размещался Тульский областной архив. В 1991 году здание храма было поставлено на госохрану в качестве памятника истории и культуры регионального значения. В сентябре 2014 года храм был возвращён верующим. В настоящее время в нём ведутся реставрационные работы.
