Schon früh muss St. Alban in Mainz in den Besitz der Büdesheimer Kirche gekommen sein. Die Zehntrechte erwarb St. Alban 1181 im Tausch gegen die Flonheimer Kirche vom Augustinerchorherrenstift Flonheim, doch muss auch St. Stephan gewisse Zehntrechte in Büdesheim besessen haben, zumindest auf einem seiner dortigen Höfe. Mit Kloster Rupertsberg gab es im 14. Jahrhundert Streit um den Zehnten auf einer Naheinsel, die sich bis in die Büdesheimer Gemarkung erstreckte.[Anm. 1]
Erstmals erwähnt wird die Büdesheimer Kirche im Jahr 1184. Damals gehörte sie dem Kloster St. Alban, auch das Patronat stand diesem Mainzer Kloster zu. Für das Jahr 1225 ist erstmals ein Priester überliefert.[Anm. 2]
Die heutige katholische Pfarrkirche entstand 1756 an der Stelle des alten Gotteshauses. Dabei wurde der romanische Westturm aus dem 12. Jahrhundert erhalten. Die Spitze des Daches mit dem schmiedeeisernen Kreuz stammt allerdings aus dem 18. Jahrhundert. 1865 wurde der Chor erneuert und die Seitenschiffe vergrößert. 1989/90 kam es zu einer umfangreichen Renovierung des Innenraums. Bei der heutigen Kirche handelt es sich um den Bautyp einer dreischiffigen Pfeilerbasilika, was bedeutet, dass die beiden Seitenschiffe durch durchlässige Säulenreihen vom Mittelschiff abgetrennt sind.
Unter der Ausstattung der Kirche gibt es einige beachtenswerte Stücke. Die Orgel mit Prospekt im Rundbogenstil stammt von 1849 und wurde von Heinrich Schäfer aus Heilbronn erbaut. Die barocken Bildwerke aus dem 18. Jahrhundert auf den Beichtstühlen stellen Halbfiguren des heiligen Aureus und der Maria (zu Justina umgedeutet) da. Auch die Rokokofiguren des heiligen Sebastian und des heiligen Michael stammen aus jeden Zeit. Die Kreuzigungsgruppe an der Außenwand des Westturms stammt laut Stifterinschrift aus dem Jahr 1654, die Assistenzfiguren wurden im 19. Jahrhundert ergänzt. Am Vorplatz westlich der Kirche befindet sich ein Kriegerdenkmal für die Gefallenen des Ersten Weltkrieges und die Lourdesgrotte, eine kleine Kapelle, die 1913 von Anton Schmidt, einem Maurermeister aus Bratislava, errichtet wurde.
Um die Kirche und östlich anschließend befindet sich der bis in die neueste Zeit - zuletzt 1916/17 - erweiterte Friedhof.[Anm. 3]