Historia mały|lewo|Mapa historyczna Warmii mały|lewo|Widok w kierunku Zalewu Wiślanego, w oddali Mierzeja Wiślana (2014) mały|lewo|Herb Fromborka w sali plenarnej staromiejskiego ratusza w Gdańsku thumb|Frombork (jako Varmia) na mapie Polski z 1570 thumb|Frombork i Braniewo na „Mapie Świętej Warmii” z 1755 Pierwsza wzmianka źródłowa o formującym się u stóp Wzgórza miasteczku pochodzi z 1278. Badania archeologiczne nie potwierdziły istnienia tutaj wcześniejszego osadnictwa. Kiedy po kolejnym powstaniu Prusów w 1275 doszczętnie spalono katedrę w Braniewie, biskup warmiński Henryk Fleming postanowił przenieść kapitułę warmińską i wybudować tu katedrę. Nazwę miasta przyjęto od Najświętszej Marii Panny, patronki katedry. Osadnicy niemieccy nazywali je – Frauenburg (polska nazwa Frombork stanowi fonetyczne przyswojenie formy niemieckiej), a kanonicy warmińscy w swoich dokumentach pisali Castrum Dominae Nostrae – Gród Naszej Pani. Przywilej lokacyjny Frombork otrzymał 8 lipca 1310 od biskupa Eberharda z Nysy na prawie lubeckim. Znaczenie miasta podniosło wybudowanie w latach 1329–1388 katedry Wniebowzięcia Najświętszej Maryi Panny i św. Andrzeja. Początkowo miasto stanowiło własność biskupów warmińskich, od 1320 należało do kapituły warmińskiej. Zwane było wówczas Civitas Warmiensis (Miasto Warmińskie).