Ursprünglich gehörte Kalsdorf zur Pfarre Feldkirchen. Der Weg zum Sonntagsgottesdienst war weit, daher gab es schon seit 1783 Bemühungen um die Errichtung einer eigenen Pfarre.
Verschiedene Gründe ließen das Vorhaben aber immer wieder scheitern:
• Einmal fehlten 54 Personen für die erforderlichen 600 Pfarrbewohner.
• Der Priestermangel ließ die Neugründung einer Pfarre nicht zu.
• Es fehlten finanzielle Mittel für die Errichtung eines Pfarrhofes in Kalsdorf.
Zwei schwere Unglücke (1802 und 1804) bei der Überfahrt auf der hochwasserführenden Mur anlässlich von Gottesdienstbesuchen waren für die Kalsdorfer ausschlaggebend, eine eigene öffentliche Kapelle zu errichten.
1813 begann man mit dem Bau an der Bundesstraße (heute Annapark und Musikschule), am 14. Juli 1872 wurde die Kapelle der HI. Mutter Anna geweiht.
Am 1. September 1945 wurde Kalsdorf Stationskaplanei. (Eine Stationskaplanei ist nach dem römisch-katholischen Kirchenrecht (can. 1214 CIC) ein für den öffentlichen Gottesdienst bestimmtes Gebäude. Sie hat eine höhere Rechtsstellung als eine Kapelle oder ein Oratorium, ist allerdings keine rechtlich selbständige Pfarrkirche.)
Am 1. Mai 1954 wurde Kalsdorf zur selbständigen Pfarre erhoben. Der Generalvikar der Diözese, Prälat Dr. Rupert Rosenberger, nahm die Pfarrerhebung und die Installation des ersten Pfarrers Anton Kogler vor.
Die Bewohner von Kalsdorf brachten ihre Freude in Form von wunderschönen Beiträgen zum Ausdruck. Bei der ersten bischöflichen Visitation der Pfarre im Mai 1958 regte Sr. Exzellenz Diözesanbischof Dr. Schoiswohl den Bau einer neuen Kirche und eines neuen Pfarrhofes an. Im November 1961 wurden die Kaufverträge für den Grund abgeschlossen, auf dem die jetzige Kirche steht.
Am 24. November 1962 erhielt Herr Architekt Ing. Worschitz aus Graz den Auftrag für den Kirchenbau.
Die Bauarbeiten begannen am 28. März 1963 unter der Leitung des Baumeisters Ing. Friedrich Bodner aus Rottenmann.
Nach den Planierungsarbeiten nahm man am 30. Juni 1963 die feierliche Grundsteinlegung unter dem Motto, „Gott zur Ehre - und den Menschen zum Heile!" vor. Im Rahmen dieser Zeremonie erfolgte die Entsühnung der Weihestätte, die Urkunde der Grundsteinlegung wurde verlesen.
Am 4. Juli 1965 fand die feierliche Einweihung der neuen Pfarrkirche „St. Paul in Kalsdorf" statt. Das Gotteshaus und die Pfarre Kalsdorf wurden dem Schutze des heiligen Apostels Paulus anvertraut. Der Tag begann mit heftigen Regenfällen, die um neun Uhr schlagartig aufhörten. Die Kirche wurde außen und innen mit gregorianischem Wasser gesegnet, die Reliquien in den Altar vom Bischof eingemauert.
Im Jahre 1965 habe ich Joseph V. Schoiswohl, Bischof von Graz-Seckau, diese Kirche und diesen Altar auf den Namen des HI. Apostels Paulus und die Reliquien der Heiligen Märtyrer Theopistus, Benig-nus und Columbanus geweiht etc.
Die von Pfarrer Otmar Rupnik in weiser Voraussicht frühzeitig bestellte und somit preiswerte neue Orgel ertönte am 3. Dezember 1967 zum ersten Mal. Der Klang dieses wunderbaren Instrumentes der Orgelbaufirma Krenn begeisterte die gesammte Pfarrbevölkerung.
Dr. Panhold von der Liturgie- und Kunstkommission aus Graz regte 1985 an, ein Gesamtkonzept zur Neugestaltung des Inneren der Kirche erstellen zu lassen.
Diplomingenieur Georg Jirak begann im März 1986 mit dieser Arbeit. Das Kirchenfenster wurde in Auftrag gegeben, im Bereich des Altares dachte man an einen Baldachin. Im Mai 1989 begann die Innenrestaurierung. Von der Holzdecke über die Betonteile bis zu allen Wandflächen erneuerte man alles. Diese Restaurierung sollte mit der Farbenpracht den Aufbruch einer lebendigen Gemeinschaft darstellen.
Beim Pfarrfest am 2. Juli 1989 wurde die renovierte Kirche von Dechant Josef Großschädl geweiht.
Bauwerksmängel am Turm und an der Pfarrkirche ließen eine generelle Außenrenovierung der Pfarrkirche notwendig werden. Eine künstlerische Gestaltung der Fassade und des Vorplatzes der Kirche wurde ins Auge gefasst. Fünf Künstler reichten Vorschläge ein. Der Pfarrgemeinderat entschied sich für die Entwürfe von Karl Klingenbrunner (Fassade) und Kurt Klöckl (Gestaltung des Kirchplatzes). Die „Paulskirche" spiegelt sich im Keramikbild (rechts vom Kreuz) wider. Beim Erntedankfest 1994 segnete Prälat Mag. Dr. Ägidius Leipold die Kirche und den neu gestalteten Kirchplatz.
Das Spannungsspiel zwischen gepflasterten und begrünten Flächen lockert die Kirchplatzfläche auf. Die Steine in unterschiedlicher Höhe stellen eine Gruppe dar - sie verkörpern nicht nur Gemeinschaft, sondern auch Begegnung. Symbole des Lebens werden zum Ausdruck gebracht.
2002 Bei der Generalsanierung des Glockenturmes, wurde auf dessen Spitze auch ein Kreuz errichtet.
Seit 2006 gibt es den Pfarrverband mit der Pfarre Fernitz. Als der damalige Pfarrer Provisor Mag. Dr. Boguslav Swiderski nach Stainz wechselte wurde aus den Pfarren Kalsdorf und Fernitz ein Pfarrverband.
2015 feierten wir 50 Jahre Pfarrkirche St. Paul