Die Kirche zu Klein-Winternheim war eine dem hl. Apostel Andreas geweihte Pfarrkirche, wobei ihr Patrozinium auf ein hohes Alter weist. Im Jahr 1297 wird urkundlich zum ersten Mal ein Pfarrer Jakob genannt.
Der Zehnt stand dem Mainzer Dompropst zu. Die Pfarrei wurde im 15. Jahrhundert vom Stift Mariengreden, später vom Mainzer Erzbischof besetzt. Noch im 16. Jahrhundert war die Kirche Filiale von Ober-Olm. Dies geht wohl auf die Entstehungszeit der Ober-Olmer Kirche in der Merowingerzeit zurück, auf die hin Klein-Winternheim (wie auch ursprünglich in der weltlichen Güterverwaltung) orientiert war. Schwer zu erklären sind Rechte der Grafen von Sponheim an der Klein-Winternheimer Kirche; sollten sich die diesbezüglichen Belege tatsächlich auf unseren Ort und nicht auf Groß-Winternheim bei Ingelheim beziehen, so könnte dafür nur eine sonst nirgends belegte Belehnung oder Verpfändung verantwortlich sein.
Der Pfarrhof wurde 1460 in der Fehde zwischen dem Kurfürsten von Mainz und dem Pfalzgrafen Friedrich niedergebrannt und nicht wieder aufgebaut. Anfangs wohnte der Pfarrer in einem Privathaus, später wurde die Pfarrei mit der Nachbarpfarrei Ober-Olm vereint. Erst 1841, nachdem ein neues Pfarrhaus gebaut war, wurde die Pfarrei neu errichtet.
Die jetzige Kirche wurde 1711 neu erbaut, brannte aber am 23. Mai 1811, von einem Blitz getroffen. teilweise ab. Die Kirche wurde nach ihrer Wiederherstellung im Jahr 1819 wieder in Gebrauch genommen. Der Turm mußte allerdings wegen Baufälligkeit bis auf das Fundament niedergelegt werden. 1895 wurde die Kirche bedeutend vergrößert und ein neuer Turm hochgezogen. Die sogenannte alte Sakristei, am heutigen Chor nordöstlich angebaut, könnte der Chor der kleinen, romanischen Kirche sein. Das Chorfenster in der gleichen Richtung hat noch gotisches Gewände.