Prölsdorf wird erstmals in einer Urkunde des Grafen Otto von Wittelsbach erwähnt. In dieser Urkunde tritt ein Engelmar von Praeliusbedorf, ein Ministeriale der Bamberger Kirche, als Zeuge auf. Der Name "Preelsdorf" = "Sumpfland" erklärt sich aus seiner ursprünglichen Lage im Sumpfland.
Die Pfarrei Prölsdorf wird erstmals im katholischen Messbuch der ebrachschen Kirche zu Theinheim erwähnt. Ein Heinrich Plebanus sei der erste Pfarrer in Prölsdorf gewesen.
Prölsdorf wird "Breldsdorf" genannt.
Die erste Pfarrkirche in Prölsdorf wird erbaut.
Folgende Filialorte gehören zur Pfarrei Prölsdorf: Spielhof (seit dem 15.Jahrhundert), Schindelsee (um 1695), Kehlingsdorf (1714), Fürnbach (1721).
Prölsdorf ist Gerichtsort.
Die erste Pfarrkirche wird abgerissen und neugebaut.
Unter dem Würzburger Fürstbischof Julius Echter werden folgende bauliche Maßnahmen an der Pfarrkirche Prölsdorf vorgenommen: Im Jahr 1591 erhält die Kirche neue Glocken. Im Jahr 1595 wird die Kirche renoviert, ein neuer Predigtstuhl wird eingebaut und ein Stück der Kirchenhofmauer wird errichtet. Im Jahr 1599 wird der Kirchturm und Kirche neu gedeckt.
Konrad Dorsch wird erster protestantischer Prediger in Prölsdorf. Ob die nachfolgenden Pfarrer Protestanten waren, ist nicht nachweisbar, aber wahrscheinlich, da der Protestantismus in der Umgebung Prölsdorfs viele Anhänger hatte.
Die Prölsdorfer Pfarrer Johannes Weller und Georg Weinmann sind Lutheraner.