История Петропавловского храма, как это ни покажется странным, связана с эпидемией холеры, свирепствовавшей в Коломне и других городах Московской губернии в 1770 г. По указу императрицы Екатерины II с 1771 г. были запрещены все захоронения возле приходских церквей в черте города. Отныне полагалось хоронить умерших за городской заставой.
В 1775 г. у Рязанской заставы было открыто Петропавловское кладбище. Тщанием коломенского купечества в 1779 г. здесь построили каменную церковь во имя Святых первоверховных апостолов Петра и Павла. Это было здание в стиле барокко, с двусветным четвериком на белокаменном цоколе. Четверик украшен рустом, пилястрами, нарядными наличниками и карнизом, над которым возвышается купол с круглыми окнами и световым барабаном, увенчанным единственной главкой. В 1833 г. к храму пристроили небольшую теплую трапезную с приделом во имя Святого апостола Андрея Первозванного. С середины XVIII в. рядом с храмом находилась каменная богадельня для воинов-ветеранов. Церкви также принадлежал двухэтажный каменный дом, стоявший на кладбище. Вверху находилось помещение для церковного сторожа, внизу — для могильщиков. В 1818 г. купцом Фирсом Ивановичем Бочарниковым церкви была предоставлена лавка. Из сумм, выручаемых с неё, три части, по воле вкладчика, употреблялись на содержание священно- и церковнослужителей. Своего причта при церкви не было, службы исправляли коломенские священнослужители понедельно. В 1880-е годы при храме существовало братство во имя святителя Николая. Под руководством священника Иоанна Фоминцева оно оказывало помощь нуждающимся ученикам Коломенского Духовного училища. Колокольня кладбищенской церкви строилась на средства коломенского купца И. И. Шкарина в 1890 г. В 1891 г. на нее водрузили новый колокол весом в 701 пуд, отлитый на средства В. С. Миляева, Шкариной, Макеевой и других прихожан. Но на пороге уже был новый век, принесший коломенским церквам немало бед и разрушений… В 1908 г. была построена ограда кладбища с тремя каменными часовнями, надвратной колокольней и боковыми воротами.
Трапезная храма очень декоративна: покрыта узорной кирпичной резьбой, украшена ложными колоннами с эффектным завершением в виде кокошников. Середину южного и северного фасадов венчают декоративные главки — по три с каждой стороны. Седьмая главка помещена над западным входом. В этой части храма, как говорят знатоки, лучшая акустика в городе, по крайней мере, одна из лучших, соперничающая с храмом Вознесения Господня. Звонницу и купола снесли в 1930-е гг., но храм продолжал действовать с перерывами, вплоть до закрытия кладбища в 1942 г. Власти несколько раз арестовывали его священнослужителей. Один из них — священник Николай Алексеевич Лебедев, родной брат епископа Шлиссельбургского Григория (Лебедева), был арестован и казнен в 1936 г. Диакон Петропавловского храма, отец Григорий Самарин, канонизирован в лике Святых в составе Собора новомучеников и исповедников Российских в 2002 г. После того, как службы в церкви Святых первоверховных апостолов Петра и Павла окончательно прекратились, иконы и росписи были утрачены. Из убранства сохранилась лишь фигурная решетка на хорах.
В конце 1960-х — начале 1970-х гг. кладбище окончательно упразднили. Место, где были похоронены многие известные коломенцы, в том числе и предки святителя Филарета (Дроздова), сравняли бульдозером. 25 октября 1970 года на территории бывшего Петропавловского кладбища при большом стечении народа был открыт Мемориальный парк и зажжен Вечный огонь в память о погибших на фронтах Великой Отечественной войны земляках. В 1970-е гг. было снесено ещё несколько архитектурных памятников кладбищенского комплекса: двухэтажный дом причта и богадельня XVIII в., а также одна из трёх часовен ограды. До 1997 г. в храме располагался спортивный зал, а в 1977 г. в нем открыли музей боевой славы. В начале 1990-х гг. был восстановлен нарядный световой барабан с луковичной главкой. В 1996 г. с северной стороны храма, на месте погребения отца и родственников митрополита Филарета (Дроздова), установлен памятный крест. Православная община храма Петра и Павла зарегистрирована в 1997 г. Периодически совершаются панихиды на территории бывшего Петропавловского кладбища (позже — Мемориальный парк).
В 2003 г. общине были переданы две уцелевшие часовни — во имя преподобного Сергия Радонежского и святителя Николая Чудотворца. В 2006 г. часовня святителя и чудотворца Николая, находящаяся в ограде бывшего кладбища, была восстановлена и теперь ежедневно открыта для верующих.
