St Teilo's church is believed to have been built during the late 12th or 13th century on the site of an earlier Celtic church. Over the ensuing centuries the building was altered and extended.
The oldest parts of the present structure are the nave and chancel. During the 14th century, small chapels were built onto the north and south sides of the chancel, and during the late 14th or early 15th century the church's capacity was increased by the addition of an aisle to the south side of the nave. The old south wall was replaced by two arches, with a third arch opening into the chancel, and finally, a porch was added to the entrance door leading into the south aisle of the church.
The roof timbers are of typical early fifteenth century design (arch-braced collar-beams), though they may in fact be slightly later in date. The west wall of the nave was altered in the early 18th century (datestone 1736) and in 1810 the interior was furnished with box pews and a three-decker pulpit. Most of the stone-mullioned windows appear to have been blocked up at this time, and were replaced by new 'Georgian gothic' lancet-shaped windows. One original two-light stone-mullioned window (14/15th) survived in the south aisle. Probably the oldest surviving feature of the church is the stone font which is believed to date from the 13th century or earlier.
St Teilo's church has been refurbished as it may have appeared about the year 1530, complete with all the elements associated with a late medieval Catholic church, including a rood screen and loft (between the nave and chancel), altars, carvings and brightly-coloured paintings on all the walls.