В Новгородской 1-й летописи под 1292 г. отмечено: «Святого Федора церковь почаша здати, которая порушилась» [НПЛ, 6800]. В 1294 г. строительство церкви было закончено [НПЛ, 6802]. Первоначальная церковь, которая к концу XIII в. «порушилась», была, вероятно, построена в 1115 г.: «Заложи Воигость церковь святого Федора Тирона, априля в 28» [НПЛ, 6623]. В более поздних летописях добавлено: «Среди дву улнць — Щпркове и Разважи» [ПСРЛ, III, с. 123; IV, с. 1 сл.]. Впрочем, наличие в Новгороде нескольких Федоровских церквей не дает полной уверенности, что речь идет об одном и том же памятнике. Церковь конца XIII в. была полностью перестроена во второй половине XVII в.
В 1974 г. у здания церкви Федора Стратилата на Щиркове улице были заложены 2 шурфа (Г. М. Штендер, Н. П. Пахомов). Они показали, что в основании здания сохранились фундамент и нижняя часть стен постройки 1292—1294 гг. Однако ниже обнаружена более древняя часть фундамента, состоящая из камней на растворе с цемянкой. В кладке фундамента встречаются куски плинф толщиной 4.4 см, шириной 18 см. Древний фундамент принадлежал квадратному в плане, трехапсидному, вероятно, четырехстолппому храму. Ширина храма около 14.5 м. Судя по технике кладки и формату кирпичей, первоначальное здание относится к концу XII — началу XIII в., хотя такая дата никак не соотносится со сведениями летописей.
Макарий. Археологическое описание церковных древностей в Новгороде и его окрестностях. М., 1860, ч. 1, с. 192— 197; Штендер Г. М. О ранних Феодоровских храмах древнего Новгорода. — Памятники культуры, Новые открытия, Ежегодник 1977, М., 1977, с. 435—437.