The church's ancient origins can be traced back to the mid-6th century, when Saxon raids threatened the area. The local Welsh King Iddon sought help from Teilo, a holy man staying in nearby Llanarth, and asked him to pray for their victory against the Saxons. In response, Teilo raised a cross upon the site, a mound which had formerly been a pre-Christian religious site, and either through the power of the Lord or the power of coincidence, the Saxon raiders were repelled. In return for this spiritual aid, Iddon granted the site of the raised cross to Teilo to build a church, with the name of the village today comprising Llandeilo (The Holy Place of St. Teilo) and Crossenny (a corruption of Iddon's Cross). As for Teilo himself, he later rose to become Bishop of Llandaff, and was venerated as a saint. Later in the 13th century, the bishops of Llandaff built a manor house at nearby Hen Gwrt. This connection to the Llandaff diocese in addition to the presence of the nearby White Castle (Y Castell Gwyn) can provide an explanation for the church's current large-scale plan.

Teilo's original church was likely a humble wooden construction, nothing of which remains today. The earliest fabric of the present building dates to the late 12th century, including the rather grand 60-foot-high Early English Gothic central tower (whose style would be more at home in Northern Germany) and its supporting crossing, and the south transept, whose north equivalent presumably once matched. Two lancet windows from this period also survive at the western end of each nave aisle, confirming that these aisles belonged to the original nave. Thus, the floorplan of the original church is for the most part what is seen today, with the exception of the chancel, north transept, and west porch.

The church was extensively remodelled in various stages throughout the 14th century. Firstly, the chancel was rebuilt deflecting slightly to the south, with the present east window dating from this time, and the north transept entirely overhauled and enlarged eastwards to form a Lady Chapel. Following this work, the central nave was rebuilt in a Perpendicular Gothic style, and, probably continuing into the next century, the nave arcade pillars replaced and the clerestory level added. The Lady Chapel's east window also seems to have been replaced in the 15th century.

In the 17th century, the Lady Chapel was commandeered by the owners of the local manor house, known as Cil-Llwch (anglicised to Killough and meaning 'dusty retreat'). The chapel became a mausoleum for the manor house owners between 1697 and 1835, and as such became known as the Cil-Llwch Chapel. Soon afterwards from 1708-09, the wonderful shingled splay-foot spire was built, raising the height of the building to some 110 feet. The bell chamber was also strengthened at this time to take six new bells, cast in 1709 by Abraham Rudhall of Gloucester and recast into eight bells in 1978 by the Whitechapel Bell Foundry in London.

In 1857, the church was restored by John Prichard and John Pollard Seddon, architects to the diocese of Llandaff and who carried out the idiosyncratic restoration at nearby Grosmont. Many of the window openings were rebuilt, with the aisle windows all being from this restoration (though their differing styles may imply some kind of continuity with the design of original medieval windows formely located there). Also replaced were the main south transept window, the inner west doorway, and the majority of the church's woodwork, including doors and pews. A protruding chimney was also added to the Cil-Llwch Chapel in the 19th century. As far as 19th century restorations go, this one seems largely inoffensive, and whilst lending the inside a slightly stuffy, Victorianised feel, the historic fabric of the church seems to have been treated well for the most part.

The information here has been taken variously from the church guide (booklet available from the church), the church website, and the Cadw listing.

Llantilio Crossenny truly is located in the middle of nowhere, occupying a small corner of land between the Wye Valley and the Black Mountains. The scenery is not objectionable by any means, but as the midpoint between two stunningly beautiful areas, the environs of the village are an overlooked spot. The village itself is tucked nicely away from the main road, but the isolated houses do not form any kind of unified ensemble. The church is situated proudly upon a prominent mound at the northernmost end of the village, and as a side note has a particularly convenient car park! The building is remarkably prominent, yet still humble and characterful. The churchyard is exceptionally well kept, with many of the headstones having been arranged in a row around the border of the premises.

Entering the church through the west porch, which is unusually situated but works well with the building's dimensions, is to enter a light space which feels simultaneously exalted and homely. The clerestoried nave and whitewashed walls remove a sense of heaviness which the church would otherwise have, and which is still present in the remainder of the building. The unusually high and thin nave proportions are reminiscent of Saxon architecture, though of course having absolutely nothing to do with it. The chancel is a totally different world, with the murkiness of the crossing transfiguring the space into a darker and more powerful setting, with the scraped rubble walls and ledger stones providing sanctity, but also coldness. The Cil-Llwch Chapel is again a totally different space, with the carpeted floor detracting from both of these ends of the spectrum and instead providing a stuffy, yet well used feel.

The church is navigable and the primary points of interest are all easily visible and accessible. There is much to take in, both from the interior and exterior of the building, and the peace of the church's setting is certainly to be savoured.

One would think that the Cil-Llwch Chapel with its manorial patronage would contain the church's most fascinating memorials, but it is in fact set into the floor of the chancel where the oldest and most wonderful tombs are to be found. Several of the ledger stones date from the 17th century and are incised with a variety of endearingly rustic relief designs. The most fascinating are two showing incised effigies, and a third, which I very unfortunately managed to miss, commemorates vicar Owen Rogers (d.1660), with his slab showing three candles and ten angels. It is a shame that I overlooked this one, as Rogers seems an interesting character too, being deprived of his living in 1654 due to 'drunkenness and malignancy,' not the most exemplary charactaristics for a vicar to be displaying!

Nevertheless, the first of the effigial slabs commemorates Jane and John Walderne, who both died in 1620. The rudimentary inscription of the family name at the top only survives in part, but their identity has been confirmed from the parish registers, with John being a distant cousin of the diarist Walter Powell. The slab depicts Jane and John standing in prayer side by side, dressed in fine Stuart costume. They are separated by a floriated cross and stand on shields with psalters atop their heads. This strange placement would surely be more befitting of a recumbent effigy, but the foot position is rather intent on showing them as standing. Of course, it is difficult to represent recumbency in 2D, and we are talking about a craftsperson operating on a distinctly local scale here, so some allowances must be made. Below the couple are depicted their three sons, Mark, David, and Charles, the final two names of whom just barely survive inscribed below.