Nad murem zamku znajdują się cztery błękitne figury, których tożsamość nie jest całkowicie jasna: jedni widzą w nich lilie heraldyczne, inni ostrza halabardy, co pasowałoby do obronnego charakteru miasta w średniowieczu.
Historia Średniowiecze mały|lewo|Średniowieczne mury zamkowe Miasto zostało założone w XII w. przez króla Danii Waldemara I jako jedna z twierdz mających za zadanie ochronę duńskich granic od najazdów Słowian połabskich. Wykorzystywano ją również jako bazę wypadową do najazdów na ziemie Słowian. Wokół zamku rozwinęło się później niewielkie miasto, które w średniowieczu odgrywało ważną rolę będąc siedzibą dworu królewskiego. Do 1284 r. odbywały się tutaj posiedzenia Danehofu, średniowiecznego duńskiego parlamentu. W Vordingborgu król Waldemar II Zwycięski, na kilka tygodni przed swoją śmiercią, zatwierdził w 1241 r. prawo jutlandzkie. W 1324 Vordingborg był też miejscem koronacji Krzysztofa II (panującego od 1320). W 1320 w Vordingborgu u króla Krzysztofa II gościł piastowski książę Henryk I jaworskiEdward Rymar, Rywalizacja o ziemię lubuską i kasztelanię międzyrzecką, w: Śląski Kwartalnik Historyczny Sobótka, nr 4/1979, s. 486.