Der Ort wird erstmals 779 in einer Schenkung an das Kloster Lorsch genannt. Später findet sich Heidesheim im Besitz des Mainzer Klosters Altenmünster. Unter den Lehensleuten des Klosters war ein gewisser Hardegen von Winternheim, der angeblich Anfang des 13. Jahrhunderts die von Wassergräben umflossene Turmburg Windeck errichtete. Wenn auch der Erbauer der Burg nicht sicher belegt ist, die Anfänge der Burg gehen in der Tat in das frühe 13. Jahrhundert zurück.