Улица, на которой расположена эта церковь, с 1922 года называется Солдатской, однако до этого она была и Петропавловской, а еще раньше, в XVIII веке, именовалась Лафертовской. Интересно, что все три названия взаимосвязаны между собой и имеют непосредственное отношение к церкви, словно подсказывают, кто ее строил, кто посещал, и во имя кого ее освятили.

Уже в конце XVII века, когда территория еще не входила в черту Москвы, здесь появляется Солдатская слобода – поселение для тех, кто служил в одном из двух элитных полков того времени под командованием Франца Лефорта, знаменитого сподвижника Петра I (русское население называло его «Лафертом»). Родом из Женевы, он прошел военное обучение в Нидерландах и, стремясь построить соответствующую карьеру, отправился в Московию, где в итоге и остался, поселившись в Немецкой слободе. Вместе с Патриком Гордоном Лефорт особенно приблизился к Петру I после событий 1689 года, когда привел своих солдат в Троице-Сергиев монастырь на защиту молодого царя. Он командовал Вторым Московским выборным солдатским полком – старейшим регулярным полком в русской армии, созданным еще в 1642 году по указу царя Михаила Федоровича. Сближение Петра с Лефортом и Гордоном способствовало тому, что царь стал все чаще бывать в Немецкой слободе.

Православная церковь в новом солдатском поселении уже существовала: еще в 1613 году впервые был возведен деревянный храм в честь святого Николая Чудотворца. Однако по указанию Лефорта в 1696 году построили новый деревянный храм, более обширный и способный вместить всех солдат полка. Возможно, каменное здание появилось бы достаточно скоро, но через три года Лефорт скончался и процесс остановился. В результате каменная церковь была возведена в 1711 году и тогда же освящена.

Несмотря на существование Лефорта, который был кальвинистом, и новые веяния в архитектуре рубежа XVII–XVIII веков, Петропавловская церковь получила достаточно традиционный для допетровской России облик: здание, вытянутое по горизонтали с запада на восток, с шатровой колокольней и пятиглавием над основным объемом. Пожалуй, единственная «модная» на тот момент деталь видна под церковными главами: вместо привычных кокошников четверик венчают барочные раковины, по три с каждой стороны. В начале XVIII века такой прием использовался при строительстве церкви в честь Ризоположения близ Донского монастыря, а также храма Спаса Преображения на Песках рядом с Арбатом (обе сохранились до наших дней). Последний своим декором и размерами весьма схож с Петропавловской церковью в Солдатской слободе, да и даты их появления совпадают – 1711 год. Так что можно предполагать, что у них общий архитектор или, по крайней мере, одна артель.

Кроме главного престола в честь апостолов Петра и Павла, в церкви существует также два придела: справа – в честь Иоанна Богослова, а слева – во имя преподобного Сергия Радонежского. Над входом в храм размещена большая круглая икона Казанской Божией Матери.

Солдатское поселение сохранялось здесь до конца XVIII века. Лефортовский полк на протяжении своей истории сменил множество названий, успев побыть и мушкетерским, и гренадерским, и карабинерным. Под разными названиями он просуществовал вплоть до 1918 года, место расквартирования его менялось. Но военный характер этого района остается до сих пор: здесь находится Общевойсковая академия вооруженных сил РФ.

Церковь апостолов Петра и Павла несколько пострадала в начале ХХ века: во время московского урагана 16(29) июня 1904 года с нее сорвало кресты, оказалась повреждена крыша. Однако в дальнейшем ей удалось пережить куда более сильные бури практически без потерь: после революции она не только продолжала действовать, но и полностью сохранила свои восемь колоколов. Их даже не сняли с колокольни – редкость для 1930-х годов, так как подавляющее большинство церквей либо утратили свои колокола, либо были вынуждены их снять и не использовать. То же касается иконостаса и внутреннего убранства церкви: все это можно увидеть практически в том же облике, что и сто лет назад.