Karl Kjelstrup grunnla de katolske menighetene i Arendal (St. Franciskus) og Hamar (St. Torfinn). Han var en begavet popularisator og en avholdt sjelesørger.
Kjelstrup vokste opp i Kristiania. Familien ventet at han skulle bli prest i statskirken, som hans farfar og oldefar hadde vært. Allerede i konfirmasjonsalderen tvilte han på lutherdommen og begynte å interessere seg for katolisismen. Til familiens fortvilelse konverterte han etter gymnaset; hans far hadde truet med å sperre ham inne på et sinnssykehus for å forhindre dette.
Kjelstrup tok examen artium ved Otto Anderssens skole 1894 og anneneksamen 1895. Samme år ble han prestekandidat for Det apostoliske vikariat i Norge og sendt til Propagandakollegiet i Roma for å studere teologi. Han fikk lisensiatgraden 1901 og ble presteviet 2. juni samme år i St. Olavs kirke i Kristiania, hvor han var kapellan 1901–11. Fra 1907 var han redaktør for tidsskriftet St. Olav, som han forble knyttet til resten av sitt liv. Kjelstrup skrev også for andre katolske publikasjoner og i dagspressen, og han blir husket for sine mange salmer og leilighetsdikt.
1911 ble Kjelstrup sendt til Arendal for å opprette en menighet for de to katolikker som bodde der. Da han forlot byen 1921, var menigheten blant landets største, og hans personlige anseelse i byen var betydelig. Kjelstrup hadde evnen til å overvinne fordommer. Han gikk tilbake til sin redaktørpost i St. Olav og var samtidig sogneprest ved St. Olavs kirke i Kristiania fra 1923, en stilling han av helbredsgrunner måtte oppgi året etter. Biskopen bad ham om å opprette et sogn i Hamar 1924; også her bidrog hans personlige egenskaper til å skape interesse for katolisismen.
Det var Kjelstrup som forberedte og opptok Sigrid Undset (1924) og Lars Eskeland (1925) i den katolske kirke. Begge disse konversjoner vakte oppsikt og gav inntrykk av at kirken hadde betydelig fremgang i Norge, særlig blant intellektuelle og kunstnere. Dette førte til en antikatolsk reaksjon, som ble en belastning for de fåtallige norske katolikker. Særlig Martha Steinsvik hadde et lydhørt publikum for foredrag og artikler som skulle avsløre den katolske kirkes skyggesider.
1931–34 var Kjelstrup tilbake som sogneprest i St. Olav i Oslo; etter eget ønske overtok han Kristiansand (St. Ansgar) 1934 for å få mer tid til å skrive. Sviktende helse og syn gjorde at han trakk seg helt fra menighetsarbeid 1940. De siste årene av sitt liv var han sjelesørger ved St. Josephsøstrenes aldershjem Vor Frue Villa i Oslo.
I ettertiden er Kjelstrup mest kjent for sin bok Norvegia Catholica (1942), som behandler den katolske kirkes historie i Norge fra 1843. Dette er et samvittighetsfullt og omfattende historisk arbeid. Han skriver lojalt, men ikke ukritisk om kirkelige autoritetspersoner og deres avgjørelser. Historien tolkes imidlertid ut fra tidstypisk katolsk triumfalisme og personlig overbevisning: Kjelstrup var forvisset om at Norge igjen ville bli katolsk.
Kjelstrup tilhørte i over 40 år dominikanernes “tredje orden”, en krets av legfolk og prester som identifiserer seg med og støtter ordenen uten selv å gå i kloster. Da brødrene kom til Norge 1920, fant de at Kjelstrup på sitt vis hadde banet veien for dem. Han bad om å få avlegge de evige ordensløfter på dødsleiet, men døde før dette kunne innvilges.
Karl Kjelstrup ble æresdoktor i teologi 1924 og pavelig kammerherre og monsignore 1925.