Einer uralten Mainzer Überlieferung zufolge soll Crescenz, ein Schüler des Apostels Paulus, in der Gegend von Mainz gepredigt haben und der erste Bischof dieser Christengemeinde geworden sein. Sicher ist, dass der heilige Paulus kurz vor seinem Martertod seinen Jünger Crescenz nach Gallien sandte, wo er die Kirche von Vienne gründete, dann zum Rhein gelangte und die Kirche von Mainz gründete. Ein vorzügliches Verdienst an der Christianisierung von Mainz gebührt der 22. Römischen Legion, die an der Zerstörung Jerusalems teilnahm, von da an viele Christen unter sich zählte, um das Jahr 70 an den Rhein verlegt wurde und die christliche Lehre verbreitete.
Gegen Ende des dritten und am Anfang des vierten Jahrhunderts blühte das Christentum schon an beiden Ufern des Rheins. Der alemannische Häuptling Rando hatte schon lange gegen Mainz Böses im Sinn. Zur Ausführung seines Vorhabens suchte er sich einen Festtag der Christen aus im Jahr 367. Während der größte Teil der Bevölkerung zum Gottesdienst in der Kirche versammelt war, brach er unversehens in die Stadt und führte viele Gefangene und große Beute hinweg. Ähnlich wurden bald nach dem Jahr 400 wieder mehrere tausend Einwohner von Mainz in einer Kirche erschlagen. Der Bischof Aureus nebst seiner Schwester Justina wurde von den Hunnen in Mainz gemartert.
Um diese Zeit (zwischen 380 und 400) starben zu Mainz des Martertodes die heiligen Alban und Theonest. Von ihnen berichtet ein altes Passionale folgendes:
„Die heiligen Theonestus und Albanus waren Christen und hatten Gott lieb. Sie dienten ihm mit Fleiß Tag und Nacht. Albanus wurde Priester, Theonestus nach einiger Zeit Bischof. Damals hatten die Christen von den Arianern viel zu leiden. Da gebot Honorius, dass beide Teile in der Stadt Karthagena zusammen kommen sollten, den Streit zu schlichten. Es erschienen 600 Bischöfe, unter ihnen Theonestus. Da bewährten die Christen ihren Glauben und machten die Ketzer schweigen. Dafür aber trugen dieselben dem Theonestus großen Hass nach, jagten ihn von seinem Stuhl und trachteten ihm nach dem Leben. Darum ging derselbe mit seinem Kaplan Albanus und Ursus zum Papst nach Rom. Der heilige Vater nahm ihn mit Freuden auf und sandte ihn nach Toscana, Ligurien und Mailand, um den christlichen Glauben zu predigen. Überall bekehrten sie viel Volk. Hernach kam Theonestus nach Augsburg, wo er seinen Kaplan Ursus zurückließ. Denselben töteten die Ketzer. Theonestus zog nach Donauwörth und weiter nach Mainz, wo die Irrgläubigen gerade in jenen Tagen den Bischof Aureus vertrieben hatten. Theonestus und sein Kaplan Albanus fürchteten sich jedoch nicht und predigten das Wort Gottes. Der Bischof Aureus kehrte in sein Bistum zurück, ward aber ergriffen und getötet. Jetzt predigten die fremden Missionare umso eifriger, bis eines Tages die Irrlehrer aufstanden, den Albanus während des Gebetes ergriffen und enthaupteten. Nun fuhr seine Seele zu den ewigen Freuden, sein Haupt aber nahm er in die Hand und trug es bis zum Ort, wo er begraben sein wollte. Dort legte er es nieder und wurde von seinem Bischof Theonestus mit großen Ehren bestattet im Dom zu Mainz. Dieses brachte allen viel Gnade bei Gott. Auch Theonestus wurde getötet. – Nun helf uns Gott, dass wir auch zu ihm kommen! Amen.“
Über dem Grab des heiligen Albanus wurde zu Mainz die Albanskirche erbaut, und mehrere Kirchen wählten den heiligen Märtyrer zu ihrem Patron.