Bereits im 9. Jahrhundert wird eine Kapelle in Kostheim erwähnt, die König Ludwig um das Jahr 850 der Salvatorkapelle zu Frankfurt, dem späteren Domstift, schenkte. Eine Pfarrkirche wird erstmals im 13. Jahrhundert genannt, 1277 kommt urkundlich der Vikar Hermann vor. Die Kirche war dem hl. Kilianus geweiht. Das Patronatsrecht über die Kirche stand der Äbtissin des Nonnenklosters Altmünster in Mainz zu, seit 1239 dem Konvent dieses Klosters. Das Recht, den Pfarrer zu bestimmen, schloss die Pflicht ein, diesem den Lebensunterhalt zu finanzieren. Der Pfarrer hatte deshalb Anspruch auf jährlich 500 Malter Korn, 15 Malter Hafer und 6 Ohm Wein. Als weiteres Einkommen stand ihm der sog. Blutzehnte zur Verfügung.
Die alte Kilianskirche wurde 1766 wegen Baufälligkeit niedergelegt, der Neubau mit einem prächtigen Turm bis 1769 vollendet. Man rühmte sie als die schönste Barockkirche am Untermain. Für den Bau dieses Gotteshauses hatte Maria Felicitas Freifrau von Berberich (um 1707–1764) Geld, Gold und Edelsteine gestiftet. St. Kilian war so repräsentativ, dass der Mainzer Weihbischof von Scheeben, ein Studienfreund des aus dem Eichsfeld stammenden Kostheimer Ortspfarrers Jakob Saul, 1777 dort acht Kandidaten zum Priester weihte.
Diese Kirche fiel aber wenig später den kriegerischen Ereignissen während der französischen Besetzung der Rheinlande zum Opfer. Sie wurde 1792 niedergerissen, die nicht mehr aufbaufähigen Überreste 1795 gesprengt. Erst 1836 wurde eine neue Kilianskirche auf den Fundamenten der Vorgängerkirche in Angriff genommen und 1895 durch ein Seitenschiff erweitert. Im Turm wurden drei Glocken in der Stimmlage E, Fis und Gis aufgehängt. Sie wurden 1893 von Andreas Hamm in Frankenthal gegossen. Die größte (17,4 Zentner schwer) trug die Aufschrift "St. Maria, ora pro nobis", die mittlere (12,6 Zentner) "St. Joseph, ora pro nobis" und die kleinste (8,8 Zentner) "St. Michael, ora pro nobis".
Im 2. Weltkrieg wurde der Bau stark in Mitleidenschaft gezogen, die Schäden wurden jedoch bald behoben, so dass sich die Kirche aus rotem Sandstein wieder in ihrer alten Gestalt präsentiert. Von der später erworbenen Ausstattung sind hervorzuheben eine wertvolle Pieta von 1760, eine gestiftete alte Ikone in einem Rahmen von A. Predohl und die Kreuzigungsgruppe in der Apsis mit den Figuren von Maria und Johannes, die 1680 in einer badischen Schnitzschule hergestellt wurden.