Zur ältesten Geschichte der Kirche und Pfarre sind nur sehr dürftige Nachrichten auf uns gekommen. Wer dieses Gotteshaus gebaut hat, ob die Herren von Zelking oder ein frommer Besitzer des Edelhofes in Verbindung mit Wohltätern aus der Gemeinde, ebenso wann der erste Stein in den Grund gesenkt wurde, darüber gibt nicht einmal eine Sage geschweige denn eine schriftliche Urkunde eine Vermutungen bekräftigende Auskunft. Nur soviel weiß man, dass ein Stiftungsbrief über einen Jahrtag zur Pfarre Matzleinsdorf vom Jahre 1350 abschriftlich vorhanden war, worin „Herr Simon, zu denselben Zeiten Pfarrherr zu Matzelsdorf
“ ausdrücklich vorkommt. Diese wichtige Urkunde ist aber in Verlust geraten und keine Hoffnung zum Wiederauffinden derselben übrig. In einer „Specification, was für briefliche Instrumenta zur Kirche zu Zelking u.s.w. gehörig“ vom Jahre 1639 im (ehem.) herrschaftlichen Archive zu Matzleinsdorf heißt es: „Num. 14. mehr ein Stiftsbrief-Abschrift zur Kirchen Mazlstorff de A(nn)o. 1350, hievor signirt No. 19“.In der von der Herrschaft Zelking zu Matzleinsdorf an das Kreisamt des Viertels ob dem Wiener=Walde zu St. Pölten und von diesem an die niederösterr. Landesregierung abgegebenen Ausfüllungen der Allerhöchst vorgeschriebenen „Directiv=Reguln=Tabell, nach welchen sich bei dem vorhabenden Pfarreintheilungsgeschäft zu Matzleinsdorf und Erlauf zu richten ist
“ beantwortet dd. Matzleinsdorf 28. October 1782, wird zu Num. 4 als Beilage D der obige Stiftsbrief oder vielmehr die Abschrift desselben angeführt; auch in früheren Schriften über die mehrmals verlangte Anstellung eines Seelsorgers, doch nur im Allgemeinen und ohne nähere Angaben, darauf hingewiesen. Nach den von dem Herrn Abte Wilhelm Eder selbst zu Wien eingeholten sorgfältigen Erkundigungen ist bei der betreffenden Behörde wohl noch die Tabelle vorfindig, deren Beilagen aber (also auch die fraglichen) leider cassirt wurden, auch im Herrschaftsarchive keine Abschrift.Ein „Extractus Matriculae Officialatus Passaviensis de anno 1429 Folio 38“ gibt an: „Mezleinstorff, III. P. (3 Pfund Pfennige, als geistliche Steuer an den Bischof, wofür eine spätere Abschrift III, Floren. setzt) Patronus Plebanus in Melck.“ Ferner kommt in einem alten Verzeichnis aus dem 15. Jahrhundert: „All (alte) Phar (Pfarre) in Oesterreich under der Enns“, in einem Codex der kaiserlichen Pfarre Metzleinsdorf vor; deßgleichen in einer 1476 gemachten Abschrift eines solchen Verzeichnisses im Archiv des Stiftes Schotten zu Wien, und zwar mit dem Beisatz, dass der Pfarrer zu Melk der Patron der Pfarre Matzleinsdorf sei (ehem. Herrschaftliches Archiv zu Matzleinsdorf). Notaten aus den Handschriften der Hofbibliothek, dem Verfasser dieser Geschichte mitgetheilt von Joh. V. Frast. – Klein’s Gesch. d. Christenth. in Oesterr. u. Steiermark, III. Bd. S. 279).
Aus dem sehr reichhaltigen Archiv der aufgehobenen Kartause Gaming kennen wir bisher die älteste Urkunde, welche uns nach dem Pfarrer Simon den Namen eines Pfarrers von Matzleinsdorf und einen von ihm geschlossenen Kaufvertrag kundgibt. Es verkauft nämlich zu Wien am St. Jorigenabend (23. April) 1368 Johanns, Pfarrer zu Metzleinstorf, nach dem Rat des Lehensherrn (Patrons) seiner Kirche, Herrn Chunrats, Pfarrers zu Melk, und mit seines Bergmeisters Hand, Ottens von Teben zu Grinzing, Bergmeister der geistlichen Herren zu Gaming, einen Weingarten an dem Schenkenberg (zu Grinzing/Wien), welchen Herr Stephan, weiland Pfarrer zu Melk, zu der ehegenannten seiner (des Pfarrers Johann) Kirche „durch seiner Seele Heil willen“ geschafft (vermacht) hat, um dritthalb und zwanzig (22½) Pfund Wiener Pfennige dem Wisenten (Wisento) von Frueling, Bürger zu Wien, und fertigt den Kaufbrief mit seinem und dem Siegel des ehegenannten (vorhergenannten) Lehensherrn und des obersten Bergmeisters Gottfried, Priors zu Gaming (Smitmer Codex diplomaticus austriacus Tom. II. Num. 399, im k. k. geh. Archive).
Eine spätere Urkunde hat sich durch den besonderen Zufall bis in unsere Tage erhalten, dass die Gemahlin des Johann Augustin Walpraun, welcher noch 1705 Pfleger oder Verwalter zu Zelking und Matzleinsdorf war, dem Stiftskämmerer (Schatzmeister) Maurus Heindl zu Melk dieselbe zur besseren Aufbewahrung daselbst aushändigte.
Es ist diese Urkunde der Stiftungsrevers (respektive Stiftungsbrief), gegeben 1411 am Mittichen nach Ruprechtstag (29. März), wodurch Leupold, Pfarrer zu Meczleinstorff, erklärt, dass ihm der Edle Herr, Herr Stephan von Zelking, sein rechter Erbvogt der benannten Pfarrkirche, und die ganze Gemeinde daselbst zu Matzleinsdorf eingeantwortet und übergeben haben zwei Weingärten, wovon einer gelegen ist zu Pechlarn an dem Berg, der andere zu Krummnußbaum, jeder Ein Viertel, und jeder mit jährlich drei Pfennigen in den Pfleghof (Amtshaus des Bischof von Regensburg) zu Pechlarn dienstbar. Diese zwei Weingärten hat der Ehrsame Herr Peter, gewesener Pfarrer des Gotteshauses zu Matzleinsdorf seliger, als sein rechtes erkauftes Erbe und eigenhaftes väterliches Erbgut hinterlassen und zu einem ewigen Jahrtage zur Kirche zu Matzleinsdorf vermacht. Der Pfarrer Leopold verpflichtet sich also, jährlich am nächsten Sonntag nach Kreuzerfindung diesen Jahrtag zu begehen, und zwar des Nachts (am Vorabend) mit einer gesungenen Vigil, des Morgens mit einem gesungenen Seelenamte, mit einem gesungenen Amte von Unserer Lieben Frau ihrer Schiedung und mit zwei gesprochenen Messen darunter, wofür er den Priestern Essen und Trinken und jedem einen großen Pfennig geben soll. An der Urkunde hingen die Siegel des Pfarrers Leopold und der Zeugen. Diese waren die Edlen Hanns der Gotsberger und Hanns der Mannsreutter (* Keiblinger, Band II, S. 308–312).
(*) Der am 12. November 1574 bestätigte neue Pfarrer zu Melk und Matzleinsdorf, Dechant Michael Span, erschien am 15. September (1575?) vor dem Consistorium im Passauerhofe zu Wien mit der Anzeige: Nachdem er auf die ihm vom Bischofe Urban verliehenen Pfarre Melk „sammt dem dazu gehörigen Filial Metzleinsdorf investiert worden, haben sich doch der Edl und Veste Christoph Straub vor kurzer Zeit die Kirche zu Metzleinsdorf zu versperren und die Schlüssel dazu von den Zechleuten mit Gewalt zu sich zu nehmen unterstanden, also daß der heilige Gottesdienst und Predigt etlichenmal hat müssen auf dem Freithof (Friedhof) vor der Kirchenthür verrichtet werden, mit Fürgeben, er sei über solches Filial Lehenherr (Patron) und der Wohlgeborne Herr von Starhemberg Vogtherr; der Bischof und sein Official habe allda nichts zu schaffen; Herr von Starhemberg habe die Rechnung schon über 100 Jahre gepflogen“. – Was weiter geschah, liegt nicht vor; augenscheinlich haben sich aber der Dechant oder der Schriftführer im Namen geirrt; denn niemals sind die Herren von Starhemberg, wohl aber die von Zelking Vogtherren der Kirche und der Pfarre Matzleinsdorf gewesen (* Keiblinger, Band II, S. 314/315).
(*) Spann war seiner schweren Aufgabe nicht gewachsen, denn in einem Schreiben des Abtes Urban an den Fürstbischof von Passau wird Spann als ein Mann, „welcher sich unter dem Deckel eines getreuen Hirten eingeschlichen habe, aber der katholischen Religion ganz widerwärtig, sehr schädlich und verderblich befunden“, beschrieben. Dass diese Beschuldigung nicht übertrieben war, geht daraus hervor, weil derselbe 1578 seiner sektiererischen Grundsätze wegen von dem Konsistorium in Verhaft genommen und ungeachtet seiner am 9. April 1579 gegebenen Erklärung: „man solle ihm die Pfarre lassen, er wolle durch einen katholischen Priester den Gottesdienst halten lassen“, noch in eben diesem Jahre wegen seines Abfalles von der katholischen Religion durch den Offizial Doktor Thomas Raidl abgesetzt (* Keiblinger, Band II, S. 36).
(*) Die Dechanten und Pfarrer zu Melk schrieben sich hinfort „Pfarrer zu Melk und zu Matzleinsdorf,“ wie z. B. Parzer, Prätorius, Dobler, Kaltenegger, Schwindt, Hoffmann und noch Pilsel, der Letzte von ihnen, und ließen die Filialpfarre durch ihre Kooperatoren versehen, an jedem dritten Sonntag und mehreren Feiertagen in der Kirche zu Matzleinsdorf den Gottesdienst abhalten, zeitweise auch Taufen hier vornehmen und Verstorbene des Ortes im hiesigen Friedhof begraben. Der ohnehin baufällige Pfarrhof fiel in Trümmer, wovon die letzten Reste im Jahre 1785 weggeschafft wurden, um dem neuen Pfarrhause Platz zu machen. Die geringen, noch vor der Begierde nach fremden Gute geretteten Renten der Pfarre wurden gleichfalls der Pfarre Melk zugewiesen und von den dortigen Pfarrern ohne Widerrede genossen. Neue Streitigkeiten entstanden, nachdem das Stift Melk durch den mit dem Hochstifte Passau geschlossenen Tauschvertrag vom 11. Juni 1693 zum Besitz der Pfarre Melk mit deren Filialen Matzleinsdorf und Maierhöfen gelangt war, wodurch zugleich die Lehenschaft oder das Patronat über die eingegangene Pfarre Matzleinsdorf, welches der Pfarrer zu Melk ausgeübt hatte, an die Abtei Melk überging (* Keiblinger, Band II, S. 315).
(*) In seiner lebhaften Freude über die nach langen Bemühungen so glücklich zu Stande gebrachte Pfarrauswechselungs-Konvention hatte der Abt Gregor angeordnet, dass dieses Ereignis am Jahrtage desselben durch ein Hochamt in der Pfarrkirche zu Melk gefeiert werden sollte. Als dieses zum ersten Mal zu geschehen hatte, lud er alle Pfarrkinder durch Verkündigung von der Kanzel und durch ein an die Kirchentüren zu Melk, Matzleinsdorf und Mairhofen angeheftetes Edikt vom 6. Juni 1674 dazu ein. Dieses Edikt wurde zu Matzleinsdorf unbedachter weise weggenommen, in das Schloss Zelking gebracht und von den beiden Pflegern an ihre Herrschaften nach Wien geschickt, deren Ansehen sie durch dasselbe „höchst geschmälert, auch die uralte Pfarre Matzleinsdorf geschwächt“ sahen. Der Besitz der Herrschaft Zelking war nämlich damals noch streitig zwischen dem Marchese degli Obizzi und dem Grafen Johann Joachim vom Sinzendorf; daher nahmen auch zwei Pfleger an der Verwaltung Theil: Andreaß Royß für dem Marchese, der zu Leiben wohnende Johann Augustin Waloraun für den Grafen. Der Titel des Marchese ist: Ferdinand Marchese degli Obizzi, kais.-kön. Kämmerer, Hofkriegsrath, General=Feldwachtmeister, Stadtguardi=Oberstlieutnant zu Wien, Besitzer der Herrschaft Zelking. Man stieß sich vorzüglich daran, dass diese nur eine Filiale genannt wurde (obwohl sie im Tauschvertrage selbst nicht anders heißt), und bei dieser Gelegenheit kam überhaupt die Klage zur Sprache, dass der Gottesdienst zu so unbestimmten Zeiten, bisweilen am dritten, manchmal erst am vierten Sonntag gehalten werde; und dass die Matzleinsdorfer, weil sie einen eigene Taufstein und Friedhof haben, auch dort getauft und begraben zu werden verlangten (* Keiblinger, Band II, S. 315/316).

In Verwahrung: Schlichter neugotischer Schnitzaltar, bez. F. Schmalzl 1903, Statuen der hll. Petrus, Bartholomäus, Paulus, Benedikt und Florian und hl. Mönch, detto auch Ständerkanzel, Orgel von Ignaz Gatto d. J. und zwei Statuen (Maria mit Kind und Herz Jesu).