Nach der Einnahme des zuvor awarischen Gebiets durch die Bayern und Franken gelangte 836 das Gut von Kirichbach (das heutige St. Andrä v.d.H.) durch königliche Schenkung an das Hochstift Passau. Es umfasste das Gebiet vom heutigen Greifenstein bis Königstetten und Langenlebarn. Im Zuge der Kolonisierung und Neubesiedlung ließ sich um 850 der passauische Gefolgsmann Zeizo mit seinen Leuten in den Mauern des ehemaligen römischen Kastells nieder. Von ihm leitet sich der heutige Ortsname ab, der urkundlich erstmals um 971 als Zeizinmurus ("Mauer des Zeizo" - Zeiselmauer) erwähnt wurde.
Bereits im 10. Jahrhundert wurde Zeiselmauer zum Verwaltungszentrum (Hofmark) des passauischen Besitzes im Tullnerfeld und zum zeitweiligen Amtssitz des Passauer Bischofs, wenn er sich im östlichen Teil der Diözese aufhielt Passauische Hofmark & Bischofspfalz. Die älteste Nachricht vom Aufenthalt eines Passauer Bischofs in Zeiselmauer betrifft den aus Passau vertriebenen Hl. Altmann, der 1091 hier verstarb und in dem von ihm gegründeten Stift Göttweig beigesetzt wurde.
Das fürstbischöfliche Zeiselmauer war nach dem landesfürstlichen Tulln der wichtigste Ort im östlichen Tullnerfeld. Die häufige Anwesenheit des bischöflichen Hofes bewirkte Wohlstand und zog Künstler an. 1203 war Walther von der Vogelweide zu Gast am Hof von Zeiselmauer. Der Ort fand auch Eingang in das Nibelungenlied und ist Schauplatz der Minnelieder des Neidhart von Reuental.
Am Ende des Mittelalters verlor Zeiselmauer diese Bedeutung. Der bischöfliche Amtssitz wurde nach Wien und die passauische Güterverwaltung und das Landgericht wurden nach Königstetten verlegt. Ursache des Niedergangs waren die häufigen und schweren Donauhochwässer, die den Ort zunehmend in Mitleidenschaft zogen. Bis 1803 gehörten Zeiselmauer und die umliegenden Orte zum weltlichen Herrschaftsgebiet der Passauer Bischöfe.