St Mary's medieval parish church is not a single thing but a layered accumulation of decisions, compromises, and repairs spanning eight centuries, and the building shows every one of them.

The town of Callan itself was founded by William Marshall, who granted it a charter in 1217 and died two years later. Whether Marshall also built the original church is a matter of some debate: documentary references to a Thomas Parson of Callan around 1215 support the idea, though one historian, Walsh, writing in 1963, proposed instead that Hugh de Mapilton, Bishop of St. Canice's Cathedral in Kilkenny from 1251, was the more likely builder. What survives today is predominantly a mid- to late-15th-century structure, with the nave and chancel dating from around 1460, but the five-storey tower at the west end is 13th century in origin. The tower is particularly dense with incident: its upper parapet with crow-stepped crenellations was added in the 15th century, while internally the scar of a stone vault, inserted in the later medieval period and removed around 1962 because it had become unsafe, is still visible on the north and south faces. Following the Reformation the church passed to Protestant use, returning briefly to Catholics after the Rising of 1641. By 1799 the nave was already considered a ruin while the chancel remained in use as a Church of Ireland parish church. In 1837 a reroofing of the chancel required the masonry of the east gable of the south aisle to be hacked away. The south arcade, weakened by subsidence, was recorded, demolished, and rebuilt on a concrete foundation in 1959. The chancel closed for worship in 1974 and passed to State care in 1976.

The stonework repays close attention. The north doorway has unusually deep moulded jambs and a hood-moulding supported by carved angels; above it is a relief of a woman in a 15th-century double-hennin headdress, the tall conical style fashionable among noble women of the period, which the architectural historian Leask believed represented the Ormond-connected patron who funded the rebuild. The south doorway answers it with angels whose gowns dissolve into intertwined vines. The traceried windows across the aisles and chancel gables draw on a range of styles, and researchers have noted that some of the tracery patterns appear to have been copied from a pattern book of 14th-century architectural designs, with the same templates turning up on tomb panels and baptismal fonts elsewhere. A 15th-century tomb in the south aisle, probably the work of the O'Tunney workshop, one of the most active sculptural workshops in late medieval Munster and Leinster, stands where an altar once was. The piscina in the chancel, a small stone basin used for rinsing liturgical vessels, has side stones recut from a 13th-century graveslab, the earlier inscription still legible beneath its new purpose.