В писцовой книге тульского посада за 1624-1685 гг. записана «церковь деревяна апостол Петра и Павла». Находилась она «на полугоре» (т. е. на холме) в «Кузнецкой слободе за городским валом». К 1734 г. деревянная церковь обветшала и ее разобрали.
В 1736 г. построили каменный храм в честь Апостолов с приделом Мученика Иоанна Воина. В 1801 г. старый придел разобрали, и в 1802 г. построили теплую церковь с двумя приделами: справа - Мученика Иоанна Воина, а с левой стороны - Преподобного Феодосия Тотемского. В том же 1802 г. построена кирпичная колокольня.
В 1833-1836 гг. произведено расширение храма под руководством архитектора В. Ф. Федосеева, который представил проект в двух вариантах. Вместо обычного купола была сооружена ротонда со значительным
внедрением западного фасада в ранее существующее здание трапезной. Архитектурное оформление ротонды решено в лаконичных ампирных формах. Ротонда имеет второй свет из высоких полуциркульных 12 окон. Окончание всех видов работ относится к 1837-1838 гг. Открытие церкви состоялось в 1848 г., а освящение - 27 января 1874 г.
В храме находились почитаемые народом иконы Казанской и Тихвинской Божией Матери, позже перенесенные во Всехсвятский собор.

При церкви с 1891 г. открыта церковно-приходская школа.
Ввиду ветхости первоначальных конструкций шпиль колокольни в 1912-1913 гг. был видоизменен, и на верхнем ярусе установлены на четыре стороны часы. Во время Великой Отечественной войны в 1941 оставшаяся часть двух верхних ярусов колокольни во время бомбежек обвалилась в сторону ротонды, повредив часть белокаменного карниза свода и стены западного фасада. В 1978 г. колокольня была восстановлена, но со значительными нарушениями архитектурного облика.

Храм возвращён верующим, 12 июля 2011 года прошло первое богослужение за 80 лет.