Церковь Петра и Павла находится на территории Мемориального парка, недалеко от памятника воинам Великой Отечественной войны и «вечного огня», а также борцам революций 1905 и 1917 годов.
Церковь в стиле позднего барокко. Отдельно стоящая колокольня построена в 1890, обширная трапезная с приделами Андрея Первозванного и Василия Анкирского выстроена вновь в 1901. Закрыта в 1943, главка и колокольня сломаны. Отреставрирована в 1980-х. С 1997 занята музеем боевой славы.
Окружавшее церковь городское кладбище срыто в 3-й четв. ХХ в.
Звонницу и купола снесли еще в 1930 годы, но храм все же продолжал действовать с перерывами, вплоть до закрытия кладбища в 1942 г. Власти несколько раз арестовывали его священнослужителей, одним из них был — священник Николай Алексеевич Лебедев, родной брат епископа Шлиссельбургского Григория (Лебедева), он был арестован и казнен в 1936 г. Диакон Петропавловского храма, отец Григорий Самарин, канонизирован в лике Святых в составе Собора новомучеников и исповедников Российских в 2002 г.
После того, как службы в церкви Святых первоверховных апостолов Петра и Павла окончательно прекратились, росписи и иконы были утрачены. Из убранства сохранилась лишь фигурная решетка на хорах.
В конце 1960-х — начале 1970-х годов кладбище окончательно упразднили, место, где были похоронены многие известные коломенцы, в том числе и предки святителя Филарета (Дроздова), сравняли бульдозером.
25 октября 1970г. на территории бывшего Петропавловского кладбища при большом количестве народа был открыт Мемориальный парк и зажжен Вечный огонь в память о погибших на фронтах Великой Отечественной войны земляках.
В 1970 годы было снесено ещё несколько архитектурных памятников кладбищенского комплекса: двухэтажный дом причта и богадельня XVIII в., а также одна из трёх часовен ограды.
Православная община храма Петра и Павла была зарегистрирована в 1997 году, периодически совершались панихиды на территории бывшего Петропавловского кладбища (позже — Мемориальный парк).
В 2003 году общине были переданы две уцелевшие часовни — во имя преподобного Сергия Радонежского и святителя Николая Чудотворца.
В 2006 г. часовня святителя и чудотворца Николая, находящаяся в ограде бывшего кладбища, восстановлена и ежедневно открыта для верующих.
В июне 2009 года церковь Петра и павла была передана православной общине, и 12 июля, на престольный праздник св. апп. Петра и Павла, Его Высокопреосвященство Владыка Ювеналий, Митрополит Коломенский и Крутицкий отслужил Божественную литургию, первую после стольких лет поругания.
19 марта 2010 15.19