Yr eglwys gyntaf i’w chodi ar y safle yma oedd capel cenhadol yn 1872. Yn 1880 adeiladwyd eglwys haearn yn ei le, ond llosgwyd yr eglwys yn 1886. Adeiladwyd yr eglwys galchfaen bresennol mewn camau, corff yr eglwys, yr ystlys a’r groesfa yn 1887-8, y gangell yn 1894, ac yn olaf y t?r a orffennwyd yn 1911.
Y penseiri oedd Douglas a Fordham o Gaer a oedd hefyd yn gyfrifol am gynllunio nifer o adeiladau eraill yn y dref. Daeth Bae Colwyn yn blwyf ar wahân yn 1893, cyn hynny roedd yn rhan o blwyf Llandrillo yn Rhos.
