Vor langer Zeit gehörte Medlitz zur Pfarrei Mürsbach und die Christen mussten auch dort in die Kirche gehen. Das war nicht immer einfach, denn die Itz hatte immer wieder den Itzgrund überschwemmt und verhinderte so den Weg zum Gottesdienst nach Mürsbach.
Als der Medlitzer Schultheiß Georg Heinrich Plach 1724 den damals für Medlitz zuständigen Pfarrer von Mürsbach, Johann Georg Platz, einem privaten Besuch abstattete, bemerkte er im Mürsbacher Pfarrhaus in einer Ecke abgestellt, eine ca. 70 Zentimeter hohe hölzerne Muttergottes-Statue mit Christuskind, den beide Arme fehlten. Der Pfarrer wunderte sich über das gesteigerte Interesse des Schultheißen an der defekten Statue und machte sie ihm auf dessen Bitte hin bei der Verabschiedung zum Geschenk.
Diese Marienstatue hatte ungefähr seit dem Jahre 1515, also über 200 Jahre lang, in der Dreifaltigkeitskapelle zu Mürsbach gestanden. Als sie bei einem Altarumbau 1721 abgenommen und unvorsichtiger Weise zu Boden gefallen sei, seien beide Arme Abgebrochen. Seither stand sie nun im Mürsbacher Pfarrhaus.
Schultheiß Plach war von der geheimnisvollen Statue ergriffen und fuhr sie zu einem Holzbildhauer nach Bamberg, um die beiden fehlenden Arme kunstgerecht ergänzen zu lassen. Einige Woche später konnte er die wiederhergestellte Muttergottes-Statue nach Hause bringen, wo sie geschützt in einem Glasschrein in seiner Wohnung ihren Platz fand.
Fortan verrichtete er und seine Familie alle Tage ihre Gebete vor dieser von ihm zutiefst verehrten Statue. Als bald auch Nachbarn und Ortsansässige Gläubige aus dem Dorf und den benachbarten Ortschaften hinzukamen, um dort vor der wunderschönen Muttergottesstatue zu beten, aber auch um Kerzen und Opfergelder darzubringen, stellte der Schultheiß die Statue im Glasschrein öffentlich unter der alten Linde in der Dorfmitte auf, wo der Andrang der Pilger und Beter zunahm.
Mit den stattlichen Opfergeldern, die in nur vier Jahren zusammengekommen waren, erbauten die Medlitzer 1728/29 mit Zustimmung des fürstlichen Ordinariats zu Würzburg eine hölzerne Kirche. Das Muttergottes-Gnadenbild befand sich fortan auf dem Hochaltar dieser Kirche.
Am Sonntag, nach Maria Himmelfahrt halten die Medlitzer ihre Kirchweih und es werden auch Amt und Predigt gehalten. Bald kamen auch fromme Pilger und die Messbesucher wurden immer mehr. 1745 seien es sogar 400 Messbesucher gewesen, darunter ca. 300 Auswärtige. Inzwischen berichtete man auch, dass das Muttergottes-Gnadenbild geheimnisvolle Kräfte verfüge. Bald wurden auch Niedergeschlagene getröstet und Kranke geheilt. Daraufhin forderte der Würzburger Weihbischof ausführliche Berichte und Beurteilungen an.
Der durch seine Predigten zu seiner Zeit sehr bekannte Dominikanerpater Magnus Kaiser, der ein großer Verehrer der Medlitzer Muttergottes war und über 30 Jahre lang, von 1737 bis 1768, einmal wöchentlich im Medlitzer Kirchlein die Heilige Messe las, Beichten abnahm und als eine Art nebenamtlicher Wallfahrtsseelsorger fungierte, betonte er wiederholt, dass „die Medlitzer Matricula“ wirklich wahr sei.
Nach der Säkularisation von 1803 und der allmählichen Neuordnung der bayerischen Diözesen wurde Medlitz 1810 der nunmehr bambergischen Pfarrei Rattelsdorf zugewiesen.
In den Jahren 1836/37 wurde die inzwischen stark verwitterte Holzkirche mit Genehmigung des Erzbischöflichen Ordinariats zu Bamberg vom 24.04.1836 durch einen massiven Sandsteinbau mit etwas größeren Ausmaßes mit Dachreiter ersetzt. Der damals für Medlitz verantwortliche Dekan und Pfarrer von Rattelsdorf, Peter Eck, hatte sich sehr für den Kirchenneubau eingesetzt und darauf hingewiesen, dass die veranschlagte Bausumme von ca. 500 Gulden bereits vorhanden sei.
Am 30. September 1854 bewilligte die kgl. Bezirksregierung die Errichtung eines eigenen Friedhofes in Medlitz. Die Gemeinde Medlitz hatte durch ihren Bürgermeister Konrad Hennemann nach einstimmig erfolgtem Gemeinderatsbeschluss vom 16.09.1853 ein entsprechendes Bittgesuch gestellt. Im Januar 1956 fand die erste Beerdigung auf dem neun Friedhof statt.
Auf Ansuchen des zuständigen Pfarrers Georg Raab wurde am 22.12.1859 durch das Erzbischöfliche Ordinariat zu Bamberg die Lokalkaplanei Medlitz errichtet, die am 2. Februar 1907 auf Betreiben des damals verantwortlichen Pfarrers Heinrich Meixner vom Bamberger Erzbischof Dr. Friedrich Philipp Abert zur Kuratie erhoben wurde.