The present building consists of a porch, tower, nave and an apsidal chancel. The church was comprehensively restored in 1860, though many of the original Romanesque parts were retained or re-used. These include a chancel arch, arcades, a re-set doorway and several windows.

There are only six churches in England that are dedicated to St Felix, a 7thc monk from Burgundy, who is credited with converting the Kingdom of East Anglia. The dedication would support the existence of a pre-Conquest church. However, there is no mention of a church within the small manor at Felixkirk as featured in the Domesday Book. There are documentary references to lands at Felixkirk being owned by the Knights of St John as early as the 12thc (VCH, 160-162).

The pre-Conquest church would have possibly consisted of an aisleless nave and apsidal chancel. At some point in the 12thc the church would have been enlarged and the aisles added. Later, a square sanctuary was added, perhaps at the same time as the tower was constructed in the 16thc. During the restoration of 1859/60, the architect, W. H. Dykes, was clearly attempting to recreate much of the church’s Romanesque character, by retaining the original chancel arch, constructing a second arch in a Romanesque style and incorporating some surviving fragments, and including Romanesque style blind arcading around the interior of the reconstructed apse.

Pevsner (161) has suggested a date of c.1125 for the carving in the chancel arch. This seems a little early. The construction of the arch and the use of volute spirals is very similar to Helmsley, where the stone appears more worn. A date of c.1170 might be more realistic.

This is a difficult church to read, largely as a result of some very effective restoration work carried out in 1860 by W. H. Dykes. Dykes uncovered the foundations of a semi-circular apse and built the current structure according to this layout. Pevsner (161) reports being made aware of a photograph and drawing showing the E end of the S aisle as being rounded. He further cites an earlier opinion that the church originally had a round nave. There are certainly some fragments of stained glass still at the church, as well as documentary references to lands being owned by the Knights of St John as early as the 12thc (VCH p.160-162). Alhough some form of circular plan for this building at some stage in its existence might be a possibility, it would be very exceptional in this region.

Although the arch at the junction of the chancel and the apse is clearly part of the restoration, the capitals that support it exhibit some significant inconsistencies. Though the material is similar, the capitals are much more worn and the cutting of the stone appears softer than the work in the arch itself, suggesting that they were originally part of the 12thc structure.