Храм возведён по решению графини Варвары Петровны Шуваловой в память её второго мужа, француза Адольфа Полье. Проект храма и расположенного рядом склепа, для погребения праха графа, разработал архитектор А.П. Брюллов. Храм в неоготическом стиле с колокольней, увенчанной ажурным шпилем, был построен в 1831—1840 годах. Освящение церкви состоялось 27 июня 1846 года. В 1930-е годы здание храма понесло ряд утрат, в том числе был снят верхний ярус колокольни и шпиль. Некоторые работы по реставрации памятника архитектуры были проведены в 1950-е годы, но полное восстановление исторического облика церкви состоялось после 1991 года.
После смерти графа А.А. Полье в 1830 году Варвара Петровна решила увековечить его память и обратилась к молодому архитектору А.П. Брюллову (брату знаменитого художника К.П. Брюллова) с просьбой разработать проект склепа для погребения праха супруга. Склеп, в подножии холма, оформленный стрельчатой чугунной аркой в готическом стиле, был устроен в том же году. В это же время графиня обратилась в духовную консисторию с прошение разрешить над склепом постройку каменной церкви по проекту Александра Павловича Брюллова (1798-1877). Разрешение было дано, но с условием, что склеп неправославного Адольфа Полье должен находиться за церковной оградой будущего храма.
Храм был заложен летом 1831 года, но из-за сложного финансового положения владельцев усадьбы строительство затянулось на 10 лет, а освещение состоялось только 27 июня (9 июля) 1846 года. Церковь стала семейным храмом Шуваловых-Воронцовых.
Церковь святых апостолов Петра и Павла располагается на вершине холма. Она решена в неоготическом стиле со стрельчатыми окнами и одноярусной колокольней, увенчанной ажурным металлическим шпилем поднимающимся на высоту 28 метров. Кирпичные стены храма, расчленённые контрфорсами, облицованы светло-жёлтым пудостским известняком. В храме был установлен резной ясеневый иконостас, также выполненный в готическом стиле.
Примечательным событием в истории церкви святых апостолов Петра и Павла стало венчание Николая Римского-Корсакова с Надеждой Пургольд, которое состоялось здесь 30 июня (12 июля) 1872 года. Шафером на свадьбе был композитор Модест Мусоргский.
После 1917 года Петропавловская церковь оставалась приписанной к Спасо-Парголовскому храму. В 1935 году храм был закрыт. Церковное здание подверглось реконструкции, в результате которой внутри было устроено междуэтажное перекрытие, снят верхний ярус колокольни и металлический шпиль, демонтированы оригинальные оконные переплеты, утрачены иконостас и скульптуры двух апостолов. Помещение было приспособлено под физико-терапевтический кабинет санатория, который в то время размещался в бывшей Шуваловской усадьбе.
В период Великой Отечественной войны храм не получил повреждений. В 1948 году, после передачи территории бывшей усадьбы Министерству автотранспортной промышленности, здесь разместился институт токов высокой частоты им. В.П. Вологдина, а в здании бывшей церкви устроена опытная лаборатория института.
Первые работы по восстановлению исторического облика церкви Петра и Павла были проведены в 1954-57 годах. В ходе работ демонтировали междуэтажное перекрытие и восстановили оконные переплеты готического рисунка. На этом этапе работы остановились, предполагалось, что реставрация продолжиться в 1970-е годы, но большой объём работ в дворцово-парковых ансамблях пригородов не дал возможности реставраторам продолжить восстановление храма. Здание было освобождено институтом и не отапливалось, так как работы по консервации памятника не проводились с течением времени произошло разрушение кровли и нарушение гидроизоляции. К концу 1980-х годов церковное здание пришло в плачевном состоянии.
В 1991 году здание было передано Русской православной церкви, в храме возобновились богослужения. При благотворительной помощи различных организаций, частных лиц и поддержке государственной инспекции по охране памятников истории и культуры (ГИОП) были начаты работы по восстановлению памятника архитектуры в результате которых церкви святых апостолов Петра и Павла в Шуваловском парке был возвращён исторический облик.