Adeiladwyd yr eglwys yn 1837 yn bennaf oherwydd Syr Richard Butler Clough o Blas Min y Don. Adeiladwyd hi’n wreiddiol fel capel anwes i Eglwys Blwyf Landrillo yn Rhos lle’r oedd Richard Butler Clough yn warden eglwys, ac fe’i chysegrwyd i Santes Catherine o Alexandria er anrhydedd ei wraig, Catherine.
Arianwyd yr eglwys gan roddion ac roedd ynddi le i 250 o bobl gyda 150 o’r seti wedi eu neilltuo ar gyfer tlodion y plwyf. Gyda chreu plwyf Colwyn yn 1844, fe ddaeth eglwys Santes Catherine yn eglwys y plwyf.
Adnewyddwyd yr eglwys ddwywaith, yn 1871 ac yn 1891, ac mae’n debyg bod y rhan fwyaf o’r gosodiadau mewnol yn dyddio o’r adeg hynny. Adeiladwyd Ficerdy cyferbyn â’r eglwys yn 1871 ond fe’i drowyd yn fflatiau henoed Llys Madoc yn yr 1980au. Gwaharddwyd canu cloch yr eglwys yn ystod yr Ail Ryfel Byd, gan fod canu clychau eglwys yn rhybudd i’r trigolion o ymosodiad gan y gelyn. Codwyd y gofeb ryfel yn 1923.
Mae’r eglwys yn adeilad rhestredig o galchfaen lleol gyda tho llechi. Mae gan y tŵr sgŵar, un o’i phrif nodweddion, furfylchau dwbl ar hyd ei thop gyda phigau topwaith syml ym mhob cornel, a ffenestri dellt bwaog plaen islaw. Rhwng y wal murfylchog a’r ffenestri mae llin-gwrs o gerrig plaen. Mae’r cloc, ar wyneb Ffordd Abergele’r tŵr, yno ers 1890 er cof am y Parch. J. D. Jones, fu’n ficer yma rhwng 1866 ac 1887. Mae ochr hon yr eglwys yn eithaf plaen â phorth bwaog ar ei hochr orllewinol, lle mae’r dyddiad 1837 i’w weld wedi ei gerfio’n ddisylw uwchben y porth.
Mae’r talcen sy’n wynebu Church Walks yn cynnwys ffenestr fawr drawiadol gwydr lliw mewn pedair rhan a osodwyd er cof am Syr Richard. Mae wal galchfaen yn rhedeg ar hyd terfyn Ffordd Abergele’r eglwys ac yn amgylchynu’r fynwent. Mae tyllau yng ngherrig copa’r wal yn brawf eu bod cynt wedi cynnal ffens reiliau. Yn ffodus, mae’r giatiau uchel addurniadol wedi goroesi.
Yn anffodus, fodd bynnag, mae’r adeilad wedi peidio â bod yn lle o addoliad.
Y drws nesaf i’r eglwys ar Ffordd Abergele mae Clwb yr Eglwyswyr.
