Bodenfunde aus dem 1. und 2. Jahrtausend vor Christus weisen auf die sehr frühe Besiedlung der Klein-Winternheimer Gemarkung hin. Reste von Fundamentmauern und zahlreiche Fundstücke in der Flur Villkeller belegen, dass römische Familien hier gesiedelt und Heiligtümer unterhalten haben. Als besonders bemerkenswerte Funde gelten ein Brunnenstein des Mars Leucetius/Loucetius und eine kleine Metalltafel für die Göttin Nemetona von Konsul Vejento und seiner Frau Attica aus der Zeit des ersten nachchristlichen Jahrhunderts. Sämtliche Funde werden im Landesmuseum Mainz aufbewahrt.
Auch in fränkischer Zeit war die Gemarkung des heutigen Dorfes besiedelt. In der Gemarkung wurden einige Gräber aus dem 5. und 7. Jahrhundert gefunden.
Im Mittelalter gehörte Klein-Winternheim zum ehemaligen Nahegau. Im ältesten Mainzer Domnekrolog um 1100 wird Winternheim zum ersten Mal urkundlich erwähnte. Wie lange es damals schon im Besitz der Mainzer Kirche war, lässt sich nicht sagen. In der Frühzeit hieß der Ort nur Winternheim, erst später wurde das Klein- hinzugefügt, um es von dem im Selztal gelegenen Winternheim zu unterscheiden. Klein-Winternheim, dem Amt Olm zugehörig, blieb bis zum Ende des 18. Jahrhunderts beim Kurfürstentum Mainz. Die französische Okkupation des Rheinlandes brachte das Ende des Mainzer Kurstaates. Johann Wolfgang von Goethe erzählt in seiner "Belagerung von Mainz" im Jahre 1793 von einem Besuch in Klein-Winternheim bei den hier einquartierten Malern Göre und Kraus.