На юго-восточной окраине города, за пароходными пристанями, на правом возвышенном берегу реки стоит небольшой храм во имя св. Феодора Стратилата с приделом во имя муч. Иоанна Воина. Передний холодный храм позднейшей архитектуры, а задний теплый более древней с низкими сводами и узкими малыми окнами. Колокольня невысокая в древнем стиле. Храм украшен прекрасным иконостасом, золоченым через огонь. Много древних икон. Время основания первоначального храма восходит ко временам царя Иоанна Грозного. Каменное же древнее здание по стилю может быть отнесено к средине 17 столетия.
Фото Ф.Я. Баранеева // Виды Вологды. - 1887
Сохранилось предание, что Феодоровская церковь была построена по особому царскому приказу. По какому поводу состоялось такое повеление - не известно. Будто бы на этом самом месте царь Иоанн Васильевич получил известие о рождении у него сына Феодора. Так говорили старожилы и прибавляли, что при храме, долго хранилась подлинная царская грамота относительно создания храма, в последствии погибшая в пожаре (1769 г.). В отечественных и местных летописях нет указания на пребывание Иоанна Васильевича в Вологде в год рождения Феодора Иоанновича и по тому предание недостоверно.