A longstanding tradition placed the founding of St. Catherine's in 1105, but scholars have found no evidence to support this, and the Urban Survey of Dublin dismissed it plainly as without foundation. The earliest reliable reference comes from the Crede Mihi, a register of Dublin churches compiled between 1212 and 1228 during the archbishopric of Henry of London. That document places St. Catherine's among the churches of the deanery of Dublin, already established, already functioning, already drawing the administrative attention of the medieval city.

The church began as a replacement for the earlier St. Thomas's Church and was soon appropriated to the Augustinian priory of St. Thomas, a community of canons regular who held authority over the parish vicarage. It later passed into the patronage of the Earls of Meath. By 1244, a deed records one Walter Rotarius living in the house next door, a small domestic detail that anchors the building in the fabric of a real medieval streetscape. The church had a Lady chapel known variously as St. Mary's Chapel, the chantry, and St. Mary's aisle. By 1533, the Repertorium Viride, an ecclesiastical survey, noted that the building had become so ruinous that parishioners had funded its complete rebuilding. A sixteenth-century tomb belonging to the Brabazon family stood inside that medieval church, but it was removed when the structure was demolished and replaced by the present building in 1769. John Speed's map of 1610 still shows the earlier form: a rectangular building labelled 'St Cathren church', with a tower at the west end. The church retains a bell cast in 1671, though it was recast in 1896.

The church sits on the south side of Thomas Street, which is well served by Dublin Bus routes and is a short walk from the Luas red line. Rocque's 1756 map of Dublin shows the churchyard extending to the south of the building, and that graveyard is still there. A seventeenth-century graveslab was recorded within it, a modest remnant of the long sequence of burial and use that the site represents. The exterior is worth a slow look, particularly with Speed's 1610 map in mind, which is accessible digitally through Cambridge University Library, since comparing the current structure against that earlier illustration gives some sense of how thoroughly the site was reordered in the eighteenth century.