El castillo fue construido en 1175 por el rey Valdemar I como castillo defensivo y como una base desde la cual lanzar ataques contra la costa alemana. Su medio hermano construyó otro castillo en un lugar remoto, que ahora es Copenhague.

El castillo tuvo un papel importante en los conflictos de la Baja Edad Media. En 1365 se firmó en él la Paz de Vordingborg que estableció el armisticio de la primera guerra danesa-hanseática, confirmando a Dinamarca como vencedor y poder dominante en la región durante los próximos tres años. Tras la reanudación de las hostilidades, esta vez por iniciativa hanseática (en el marco de la Confederación de Colonia), el castillo y demás fortificaciones de la ciudad aguantaron dos años de asedio, siendo Vordingborg de las pocas plazas danesas que lograron resistir la presión enemiga durante toda la contienda (aunque finalmente sería la Liga Hanseática el claro vencedor en la guerra).

Unas décadas después, el castillo volvió a ser el lugar de firma de un acuerdo de paz. En 1435, los beligerantes en la guerra entre la Unión de Kalmar (de la que Dinamarca formaba parte), Holstein y la Liga Hanseática firmaron en él el tratado que puso fin a la contienda.^[2]​^[3]​

Hoy el Castillo Vordingborg es una ruina, aunque algunas partes de las paredes del anillo del siglo XIV se mantienen. La única parte totalmente conservada del castillo, la torre de 26 metros de altura (Gåsetårnet), es el símbolo de la ciudad.

• Guerra danesa-hanseática
• Guerra entre la Liga Hanseática y la Unión de Kalmar