Yn 1885, rhoddodd yr Arglwydd Windsor erw o dir ar gyfer sefydlu eglwys yn Grangetown, un o faestrefi newydd Caerdydd. Ef hefyd a fu’n gyfrifol am roi’r arian ar gyfer y costau adeiladu cychwynnol, sef £4,000. Gosodwyd y garreg sylfaen yn 1889, ac agorwyd yr adeilad gan Esgob Llandaf ar 3 Chwefror 1890. Ychwanegwyd cangell yn 1902.
Mae llyfr Pevsner, ‘Buildings of Wales’ yn disgrifio’r deunyddiau adeiladu fel ‘ecsentrig o’r mwyaf’. Mae’r waliau wedi eu hadeiladu o rwbl Pennant a cherrig nadd tywodfaen pinc Swydd Stafford. Yn yr eglwys hefyd ceir enghraifft gynnar ac anghyffredin o’r defnydd o goncrit; adeiledir prif ddarnau’r adeilad â choncrit wedi’i gymysgu â cherrig bychain, briciau wedi’u malu a cherrig mân tywodfaen.
Daeth Eglwys St Paul yn enwog yn 2005 pan ymddangosodd mewn episod o Dr. Who (Father’s Day) ac oherwydd hyn mae’n gyrchfan poblogaidd ar gyfer dilynwyr y gyfres deledu Dr Who.