The frescoes of the Church of Theodore Stratilates, likely created in the late 60s or 70s of the 14th century, were cleaned of whitewash in 1910. Although the painting has survived on most walls, pillars, arches, and vaults of the temple, it remains only fragmentary with significant losses. Nevertheless, its artistic value is great. The painting employs a monochromatic approach in red-brown tones, distinguishing it from the bright polychrome frescoes of Novgorod from that time. This brings it closer to the frescoes of the Church of the Savior on Ilyina, created by Theophanes the Greek. Some researchers consider the frescoes of Theodore Stratilates to be an earlier work of this master, while others view it as a later creation of a Novgorod artist influenced by Theophanes. The frescoes exhibit the characteristic 14th-century love for narrative and an emotional interpretation of suffering, transitioning into pathos. The compositions and figures bear the imprint of Byzantine art from the 13th-14th centuries.

The painterly texture of the frescoes of Theodore Stratilates is similar to that of the frescoes of the Church of the Savior. The base is a red-brown color, over which light pasty strokes are applied. A dark brown outline defines the shapes. However, the frescoes of Theodore Stratilates lack the virtuosity characteristic of the frescoes of the Savior. Many characters in the frescoes of Theodore Stratilates resemble those in the frescoes of the Church of the Savior. It is particularly noteworthy that secondary details of the landscape, costume, or ornament in the compositions of both churches often coincide.