Церковь эта слыла в народе под именем "царской".
Из уст в уста передавалась легенда о том, как "царь Грозный" приказал построить храм на нагорном правом берегу р. Вологды, как раз на том месте, где получил известие о рождении сына Феодора. Легенда была в духе наших предков, любивших знаменовать радостные события, постройкой храмов, но cyxиe историографы разрушили эту легенду, высчитав, что в год рождения сына (в 1557 г.) царь не мог быть в Вологде. Однако, установлено существование храмозданной грамоты, относящейся ко времени Грозного царя. Второе его посещение было в 1565 г.; возможно, что церковь построена по его воле во время этого посещения.
О постройке каменной церкви данные разноречивы: Вол. Кал. за 1893 год относит церковь к 1628 году, "Волог. Стар." - ко второй половине XVII века, а местный историк И. Н. Суворов - к первой половине XIX века. Это различие можно объяснить лишь тем, что храм много раз горел и каждый исследователь дает год перестройки. В 1769 году во время большого пожара церковь полуобгорела; ясно, что она уже была каменной, так как при отсутствии противопожарных средств в то время вряд ли можно было отстоять деревянное строение. Церковь эта ранее была приписана к тюремной, а теперь к Кирилло-Рощенской церкви.* Архитектурная внешность Феодоровской церкви мало интересна. На снимках давних времен, правда, она рисуется еще кубической формы, одноглавой, с одной абсидой, в типе храмов конца XVII столетия, но - теперешний ее вид, хотя и говорит о столь давних временах построения, вместе с тем указывает на разные позднейшие переделки. Как бы то ни было, во всяком случай куб храма с закомарами типичен для русского стиля; главка приятных пропорций; звон колокольни приятной отделки (сухарики и зубчатые пояски карнизов) - и лишь слуховые окна отделаны очень грубо и примитивно.
* У священника которой и ключ от церкви Феодора Стратилата.
Позднее крыльцо, не идущих к храму, форм деревянного зодчества. Застроенное между церковью и звонницею пространство и торчащие дымовые трубы нарушают ту живописность вида, которая могла бы получиться у церкви, благодаря ее местоположению и рощице березок, среди которых она стоит на крутом берегу реки.
Внутри церкви - поражает своею красотою иконостас. Он едва ли не лучший в смысле чистоты форм и линий стиля барокко; прелестна мелкая плоская резьба покрывающая его части; отлично вылеплены сочные лишь кое-где брошенные поверх колонок, завитки. Иконостас половины XVIII в.
В иконостасе имеются старинный иконы.
Живопись поздняя. Лишь в киоте старинная икона Спасителя; в алтаре интересен маленький иконостас с иконами.
В створке боковых иконостасных (с правой стороны) дверей интересна икона Феодора Стратилата с углублением; хорошие иконы есть еще в приделе.
Среднее большое паникадило ампирное (20 - 30-х годов XIX стол.).