Фресковая роспись церкви Федора Стратилата, исполненная, по-видимому, в конце 60-х или даже в 70-х годах ХIV века, была расчищена из-под побелки в 1910 году. Роспись сохранилась почти на всех стенах, на столбах, арках и сводах храма, но фрагментарно, с большими утратами. Несмотря на это, художественное значение росписи исключительно. Во фресках храма применен прием монохромного решения всей стенописи в красно-коричневых тонах с полным отказом от яркой, звучной полихромии других новгородских росписей ХIV века. Вместе с тем эта черта очень сближает роспись Федора Стратилата с росписью церкви Спаса на Ильине, исполненной Феофаном Греком. Роспись Федора Стратилата рассматривалась одними исследователями как более раннее произведение этого прославленного художника, другими, наоборот, как более позднее произведение какого-то новгородского мастера, испытавшего на себе сильное влияние манеры Феофана Грека. В росписи Федора Стратилата ярко выступает характерная для ХIV века любовь к повествовательной тематике, с одной стороны, и глубоко эмоциональная трактовка человеческих страданий, переходящих в патетику, — с другой. Композиции и отдельные фигуры росписи Федора Стратилата несут на себе несомненный отпечаток византийского искусства ХIII — ХIV веков.
Живописная фактура стратилатовской росписи, как уже сказано, обнаруживает ближайшее родство с фактурой фресок церкви Спаса. Тот же красно-коричневый цвет лежит в основе, по нему проложены высветленные и острые пастозные белильные мазки «движек». Темно-коричневый рисунок оконтуривает форму. Однако в стенописи Федора Стратилата приемы не отмечены той виртуозностью, которой отличаются фрески Спаса. Многие персонажи стратилатовской росписи обнаруживают ближайшее родство в своих характеристиках с персонажами росписи церкви Спаса. Особенно симптоматично, когда отдельные второстепенные детали пейзажа, костюма, орнамента или реквизита тех или иных композиций буквально повторяются в росписях этих церквей.
