Az Árpádok korában a mai Tabán helyén már áll egy királyi, exempt, vagyis a veszprémi püspök joghatósága alól kivett és az esztergomi érsek joghatósága alá tartozó templom a sasadi és örsi filiális kápolnákkal. Egyesek szerint e templom már Szent Gellért halálakor létezik Nagyboldogasszony titulussal, benne temetik el Szent Gellértet és a vértanú püspök szentté avatása után titulusát Szent Gellértre változtatják. Más vélemény szerint csak a szentté avatás után emelnek a Kelen-hegy tövében templomot, amely körül aztán a XII. sz.-ban kialakul Kispest, Kelenföld elnevezéssel a mai Tabán őse. Az ősi plébánia egy-egy papjának neve a XIII., XIV. sz.-ból ismert. Plébánosait a XIII. sz.-i okiratok még kelenföldinek mondják, de már 1330-tól budainak. – Függetlenségét a plébánia még a Vár-plébániával szemben is meg tudja őrizni. A törökök az itt működő nagyszámú cserzőműhelyrôl Debbagháne-nak nevezik a települést, amelyből a magyar a Tabán nevet alkotta. Musztafa pasa dzsámija állt a mai templom helyén. A felszabadulás után kápolnává alakítják Alexandriai Szent Katalin tiszteletére. Meghagyva a kápolnát szentélynek, 1728–36 között Obergruber Keresztély karintiai kőműves vezetésével hozzáépítik barokk stílusban a templom hajóját. A tornyot 1750-ben Nepauer Mátyás emeli és valószínűleg a dzsámiból kialakított szentély lebontása után az új szentélyt is. Az ősi plébániát 1702-ben állítják vissza, amelyet 1868-ig a Kapisztrán ferences rendtartomány atyái vezetnek. Zárdájuk 1750-ben épült. Nagy károkat szenved a templom és a plébánia 1818-ban tűzvésztől és 1849-ben a szabadságharc során. – A második világháború után a műemlék templomot (473 m2) állami költséggel hozzák rendbe. A belső liturgikus tér kialakítása Körmendy Bélának, a magyar liturgikus mozgalom úttörőjének nevéhez fűzôdik.