Im Jahr 1308 wird das Schloss Vösendorf erstmals als castrum im Melker Lehensregister samt Besitzer erwähnt. Dieser Besitzer war ein gewisser ritterlicher Wiener Bürger Namens Konrad Praitenfelder. Das Schloss selbst ist jedoch deutlich älter. Über die Erbauungsgeschichte liegen uns leider keine genauen Informationen vor, doch gibt es Hinweise, die auf eine Errichtung im ausgehenden 11. Jahrhundert schließen lassen. Interessanter, aber nicht weniger kompliziert, wird die Zeit des Hochmittelalters, in der es oft zu wechselnden Herrschaften und Besitzern kam. Nachdem sich Konrad Praitenfelder an einem  erfolglosen Aufstand gegen Herzog Albrecht I. beteiligt hatte, wurde ihm das Schloss entzogen.

Nach wechselnden Schlossherren kam das Schloss schließlich 1350 in den Besitz von Wolfgang von Winden. Die Herren von Winden, die auch Grund in Tribuswinkel besaßen, behielten Vösendorf als Lehen des Stiftes Melk mit Unterbrechungen bis ca. 1510. Eine dieser Unterbrechungen ist der Krieg des ungarischen Königs Matthias Corvinus gegen den römisch-deutschen Kaiser Friedrich III., bei dem weite Teile der habsburgischen Erblande besetzt und von Wien aus regiert wurden. Von 1487 bis 1494 wurde von Corvinus ein Burgverwalter eingesetzt, der über Vösendorf und dessen Ländereien regierte. Nach dem Tod des Ungarnkönigs zieht Maximilian I., der Sohn Friedrichs, kampflos in Wien ein und belehnt seine Treuen mit den zurückeroberten Besitzungen, darunter auch das Schloss Vösendorf.