Тамбовский храм во имя первоверховных святых апостолов Петра и Павла ведёт свою историю с 1690-х годов. Первая деревянная церковь Петра и Павла была построена на городской окраине того времени, на месте где сейчас находится областная библиотека им. А.С. Пушкина. По преданию основал и освятил храм святитель Питирим Тамбовский. Прошли десятилетия. Город разрастался, бывшие городские окраины становились центром. Храм, напротив, всё больше поддавался влиянию времени и разрушался. Стены церкви стали тесны для увеличившегося числа прихожан. Всё острее стал вставать вопрос об освобождении от ветхой церкви удобной площадки и строительстве на её месте нового большого каменного храма. И вот, в 1770 году было принято решение перенести церковь на недавно основанное кладбище за западными городскими окраинами, а на её месте заложить новый храм. В 1778 году на месте, которое ранее занимала старая церковь Петра и Павла, было закончено строительство нового каменного храма, впоследствии известного как Уткинская церковь.

После перенесения в 1771 году церкви Петра и Павла на кладбище, кладбище получило название Петропавловского. В 1820 году Петропавловская деревянная кладбищенская церковь была окончательно разобрана и отстроена заново в камне на средства тамбовского мецената купца И.В. Шихаева. Данная церковь просуществовала до разрушения в 1938 году.

В 1946 году по просьбе верующих прихода Покровской церкви, городскими властями была санкционирована постройка небольшой деревянной часовни на Петропавловском кладбище для отпевания умерших. В связи с резким дефицитом действующих православных церквей в Тамбове в те годы, в Петропавловской часовне, приходящими священниками Покровской церкви, помимо отпеваний совершались обряды крещения, венчания и другие требы. До конца 80-х годов прошлого века, церковь на Петропавловском кладбище неоднократно подвергалась гнёту со стороны советских властей. Несколько раз ставился вопрос о её закрытии или сносе.

Сейчас церковь представляет собой маленькую деревянную избу с единственной золочёной главкой на крыше. В 2005 году рядом с Петропавловской кладбищенской церковью была построена небольшая кирпичная колокольня.