Деревянная церковь во имя святых апостолов Петра и Павла упоминается в «Писцовой книге Тульского посада 1624-го и 1685-го годов», изданной И. П. Сахаровым. По словам старожилов, рассказы которых записывал в середине XIX века Н. Ф. Андреев, вначале существовала в этих краях Петровская часовня, стоявшая на названной по ней Петровской улице. Часовня получила свое наименование по находившейся в ней иконе Петра и Павла.К 1734 году церковь сильно обветшала и её разобрали. Двумя годами позже на её месте был возведён новый каменный храм. В 1802 году его перестроили. У храма появилось два придела, Мученика Иоанна Воина и Преподобного Феодосия Тотемского и была возведена колокольня.
В первой половине XIX века было принято решение о перестройке храма. Этим занялся архитектор В. Ф. Федосеев. В 1833—1838 годах вместо обычного купола была сооружена ротонда в лаконичных ампирных формах с двенадцатью полуцеркулярными окнами. Через год после начала строительства церкви в её стенах и сводах появились трещины. На целый год работы были приостановлены. Специальная комиссия определила причину повреждений, «слабость фундамента». Вместе с тем разрешение на продолжение строительства было дано, правда, с рекомендацией заменить первоначально предполагавшийся каменный купол на деревянный, что и было сделано. Осенью 1836 года храм был возведен, но внутренняя отделка, видимо, из-за недостатка средств, длилась ещё почти 12 лет. В справочной книге «Вся Тула и Тульская губерния», изданной в 1925 году, в разделе «Тульские здания, как исторические памятники» стиль церкви Петра и Павла характеризуется как «московский николаевский классицизм». Искусствовед А. А. Кипарисова в 1948 году отмечала, что Петропавловская церковь в Туле, по преданию, сооружена одним из братьев знаменитого московского архитектора Бове. Однако архивные материалы, позже обнаруженные исследователем тульского зодчества В. Н. Уклеиным, бесспорно свидетельствуют, что автором проекта был архитектор В. Ф. Федосеев.
В храме находились почитаемые верующими реликвии, иконы Казанской и Тихвинской Божией Матери, которые позже перенесли в Всехсвятский кафедральный собор. В 1891 году при храме открыли приходскую школу. При церкви имелась деревянная, под железной кровлей богадельня на шесть человек, построенная иждивением потомственного почетного гражданина С. Т. Красноглазова вместо прежней ветхой, существовавшей с 1811 года. По проекту архитектора С. М. Серебровского в 1912—1913 годы был заменён третий ярус колокольни и надстроен четвёртый, завершением которого стал высокий шпиль на полусфере. На колокольне на все четыре стороны были установлены часы.
В 1922 году «в пользу голодающих Поволжья» из храма изъяли церковные ценности. В 1930-х годах храм был закрыт. В 1941 году, во время бомбёжек Тулы немецкими войсками, верхняя часть разрушилась и обвалилась в сторону ротонды, повредив карниз и стены. В 1947 году постановлением Совета Министров РСФСР храм был включен в число охраняемых объектов архитектуры Тулы. В 1978 году колокольню восстановили, но в результате неудачной реставрации, она получила завершение, напоминавшее мусульманский минарет. В дальнейшие годы в здании храма размещался аптечный склад. В 1991 году здание храма Петра и Павла было поставлено на госохрану, как памятник истории и культуры Тульского региона.
В 2011 году церковь возвратили Тульской епархии, и началось возрождение храма. 12 июля 2011 года состоялось торжественное открытие храма, а 4 октября 2012 года по благословлению митрополита Тульского и Ефремовского Алексия на здании храма установлен новый купольный крест, а 31 декабря 2015 года он был освящён. Неудачное завершение колокольни, сделанное в 1970-х годах, было демонтировано. Сейчас идет разборка её верхних ярусов, которые при той же реставрации получились более узкими, чем были в начале ХХ века. Затем эти ярусы и шпиль будут восстановлены, в том виде, в каком они были сто лет назад. На колокольне появятся часы, как и ранее, на все четыре стороны. Все эти работы завершились в 2018 году.
