Im 13. Jahrhundert (Ablass 1292) bestand in Bechtolsheim eine Pfarrei. Die damalige Kirche stand aber nicht an der Stelle der heutigen Kirche. Ihre Mauern waren noch 1790 vorhanden. Laut einer Beschreibung vom Jahr 1612 enthielt die Kirche viele Grabsteine von Ganerben.
Die heutige Kirche ist der heiligen Katharina geweiht, sie wird auch als "Neue Kirche" bezeichnet. Zu ihrem Bau liegen nur spärliche Nachrichten vor: Genehmigung für den Neubau durch die Ganerben 1482 auf Antrag der Kirchengeschworenen. Die heutige dreischiffige Hallenkirche wurde 1482 bis 1494 von bayerischen Steinmetzen unter Leitung des späteren Leiters der Straßburger Dombauhütte Jakob von Landshut (gest. 1509) errichtet. Auftraggeber war als Sprecher der Ganerben Philipp von Dalberg. 1487 Stiftung für den Theobalds-Altar, der in die neue Kirche übertragen worden war. Der Kirchturm war ursprünglich in die Ortsbefestigung mit einbezogen und ist in seinen Ursprüngen älter als die Kirche. Bau und Unterhaltung oblagen der bürgerlichen Gemeinde, die auch die Glocken anschaffte. Ein lang anhaltender Glockenstreit um das Läuterecht wurde erst 1965 entschieden.
Nach der Reformation fiel die Kirche an die Lutheraner, diese mussten aber 1685 den Katholiken das Mitgebrauchsrecht einräumen (Simultaneum). Die Kämpfe um den Besitz der Kirche hörten nicht auf. 1741 musste die lutherische Gemeinde dem katholischen Pfarrer sämtliche zur Kaplanei gehörigen Güter und Einkünfte überlassen, den in der Kirche errichteten lutherischen Pfarrstuhl abbrechen und dafür den katholischen Beichtstuhl wieder an seinen Platz zu bringen und die abgebrochenen Chortüren wieder herstellen. Der Chor schließlich wurde den Katholiken zum alleinigen Gebrauch überlassen. So blieb es bis zum heutigen Tag. Bechtolsheim ist eine der wenigen noch heute existieren Simultankirchen in Rheinhessen (insgesamt 7).
Im Jahr 1695 brannte der Dachstuhls aus und das Gewölbe blieb längere Zeit offen stehen. Die Neueindeckung erfolgte 1704, Restaurierungen erfolgten 1887 und 1969-77.

Wappen der Ganerben in den Netzgewölben. Putz des Gewölbes 1724 erneuert (Brand 1695) und Kirche neu ausgemalt. Ausmalung 1887. Stummorgel von 1756. barocke Kanzel. Taufstein von 1530, vollständig entwickelte Renaissanceformen, für seine Zeit sehr modern.

Falkener-Gestühl: 1496 entstanden: Hinweis auf Inschrift, insgesamt 30 Bänke, erstes Gestühl in der Kirche, erst seit dem 15. Jh. Bänke für die Gemeinde (s. Lithurgievorschrift 1473, wo erstmals vorgeschrieben wird, dass die Gemeinde bei bestimmten Messhandlungen - Epistel, Predigt - sitzen soll), in einem großen Quadrat aufgestellt, Säulen integriert, alle vollständig erhalten, auch in der originalen Farbfassung, vollständig erhaltene Bänke aus dieser Zeit sind sehr selten, die meisten Gestühle in der Barockzeit durch bequemere ersetzt ("Vorteil" der ärmeren Kirchengemeinden in abgelegenen Orten), Bänke zu Blöcken zusammengefasst, Füllbretter (Lehnen und Wangen) mit farbig gefassten Flachschnitzereien verziert (Heiligennamen, Inschriften, Stifterwappen, gotische Stabranken, Blumenpötte mit Rankenwerk aus der Renaissance).

Ähnliches Gestühl in Kiedrich, jedoch stark überarbeitet. Deshalb gibt das Bechtolsheimer den Charakter der damaligen Kirchenbänke am besten wider. Reste ähnlicher Gestühle von Falkener (bzw. Schule): signiert:Weinheim bei Alzey (im 18. durch barockes Gestühl ersetzt, lediglich letzte Bank mit Inschrift erhalten), Kiedrich (erhalten, jedoch stark verändert). Unsigniert: Weinheim bei Mauchenheim (Reste der alten gotischen Bänke in barocker Orgel wiederverwendet), Manubach bei Bacharach, Udenheim (Bergkirche, kleines Chorgestühl), Mindelheim (Bayern, Kanzel und Schrank).

Zur Person Falkeners: Falkener stammt aus Abensberg in Bayern (Niederbayern, bei Kehlheim), dh. mit den Bauleuten kamen auch Holzschnitzer aus Bayern nach Rheinhessen. Er wohnte in Gau-Odernheim (Inschrift in Kiedrich). In Abensberger Urkunden ist nichts über Erhard Falkener zu finden, auch in einer Beschreibung des Ortes Abensberg von 1680 steht nichts über ihn. Möglicherweise war sein Vater Falkner am Hof des Herzogs v. Landshut oder des Grafen von Abensberg.

Das Chorgestühl aus dem ausgehenden 15. Jahrhundert ist wahrscheinlich nicht von Falkener, Parallelen zum Chorgestühl in Herrnsheim (1486), bajuwarischer Typus.

Der barocke Hauptaltar wurde 1761 vom Kloster Marienmünster bei Worms gekauft, 1699 von Franz Hügelij geschaffen. Mittelbild von Matthäus Lohmann (Himmelfahrt Mariens), darüber Gott-Vater und Christus, die die Krone für Maria halten, darüber die Taube des Heiligen Geistes. Statue links hl. Bernhard (Leiter), rechts hl. Antonius von Padua (Christus-Kind), über Tabernakel hl.Barbara (Turm), flankiert von hl. Clemens und Tiburtius (s. Inschrift rechts vom Tabernakel). Rechts vom Tabernakel Inschrift: Hinweis auf Stifterin und Baudatum 1699. Der Altar ist in seiner Originalgestalt restauriert.