Дата постройки последнего здания: 1850-1855   см. фотографии объектов той же эпохи

Первая полковая церковь Константина и Елены с походным иконостасом с 1806 находилась в старых казармах на Звенигородской ул. 20 мая 1817 в новых казармах на Рузовской, построенных Ф. Демерцовым и А. Штаубертом, была освящена церковь сщмч. Мирона. Новый проект К. А. Тона, напоминавший Благовещенскую церковь Конного полка, утверждён Николаем I 15 марта 1849. Храм заложен 29 июня 1850, строительство здания в русско-византийском стиле велось под руководством Г. X. Штегемана на средства Кабинета Его Величества, освящён 17 авг. 1855. Главный престол ап. Павла, приделы Александра Невского (правый) и сщмч. Мирона (левый). 21 нояб. 1889 под главным алтарём освящена Никольская часовня в память о спасении Императорской семьи в Борках. Церковь закрыта в марте 1930, переоборудована в картофелехранилище. Взорвана весной 1934 и к лету разобрана на кирпич.

В 1915 в подвале храма по проекту воен. инж. Е. Н. Грушецкого для павших в Первую мировую войну офицеров был создан склеп. До окт. 1917 в нем было похоронено около 30 человек.