Церковь Феодора Стратилата построена в 1782–1806 гг., как «теплый храм» при церкви Архангела Гавриила. Проект церкви приписывается архитектору И. В. Еготову.
Церковь первоначально была освящена во имя Феодора Тирона, после устройства придела Феодора Стратилата (1806 г.), а затем значительной перестройки здания во второй половине XIX в. храм приобрел современное название.
Церковь должна была играть роль не только зимнего храма при Меншиковой башне (церковь Архангела Гавриила), но и колокольни, с чем связано необычное решение ее венчающей части — над широким куполом с люкарнами (установлен на низком ступенчатом постаменте) возвышается стройная круглая башня в стиле классицизма, прорезанная высокими арками звона. Пластическую выразительность фасадам придают глубокие, стрельчатые, доходящие до невысокого цоколя оконные ниши.
В 1860–1890 гг. с севера и запада сделаны пристройки и выполнена стенопись. Иконостас относится ко второй половины XIX в.
Украшавший главный фасад храма четырехколонный портик был разобран в 1930-х гг., после закрытия церкви.
Церковь вновь была открыта в 1947 г. как подворье Антиохийского патриархата.
