Pierwsze wzmianki źródłowe o Fromborku pochodzą 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ć katedrę we Fromborku. Nazwę miasta przyjęto od Najświętszej Marii Panny, patronki katedry. Osadnicy niemieccy nazywali je - Frauenburg, a kanonicy warmińscy w swoich dokumentach pisali Castrum Dominae Nostrae - Gród Naszej Pani. Ona też zajęła miejsce w herbach miasta i kapituły.
Powstały w wyniku tego wyboru w ostatniej ćwierci wieku XIII kompleks osadniczy składał się z dwóch, całkowicie od siebie niezależnych, jednostek: zespołu katedralnego na wzgórzu i miasta nad brzegiem Zalewu Wiślanego. Każda z nich posiadała odmienne podstawy prawne. Dopiero w końcu wieku XIX tarasy górny i dolny powiązano w jeden zespół, natomiast w roku 1926 Wzgórze Katedralne i miasto połączone zostały administracyjnie.
Frombork początkowo stanowił własność biskupów warmińskich, od roku 1320 należał do kapituły. Zwany był wówczas Civitas Warmiensis (miasto warmińskie). Tak też było w istocie, gdyż Frombork był stolicą Warmii. Prawa miejskie nadał Fromborkowi biskup Eberhard z Nysy dnia 8 lipca 1310 roku.
We Fromborku przebywał Mikołaj Kopernik, który jako kanonik kapituły warmińskiej żył i pracował na Wzgórzu Katedralnym niemal nieprzerwanie od roku 1510 do dnia swojej śmierci w maju 1543 roku. Właśnie tutaj Mikołaj Kopernik opracował swoje wielkie dzieło "De Revolutionibus", które odmieniło dotychczasowe pojęcia o wszechświecie. Zespół katedralny na Wzgórzu jest klejnotem architektury na Warmii i miejscem, gdzie pochowano Mikołaja Kopernika.
Od czasów założenia życie mieszkańców miasta wiązało się głównie z rybołówstwem i rolnictwem. Z biegiem lat powstawały tutaj warsztaty rzemieślnicze świadczące głównie usługi dla kanoników i służby kościelnej. Już w średniowieczu wymieniano funkcjonowanie we Fromborku cechów krawców, piekarzy, piwowarów oraz gildii rybackiej. Po kilkakrotnych zniszczeniach zabudowy miejskiej w czasie wojen szwedzkich rozpoczyna się w drugiej połowie wieku XVII upadek gospodarczy. Pewne ożywienie daje się zauważyć po roku 1837, kiedy przeniesiono tutaj siedzibę biskupstwa.
Rozwój turystyki, który nastąpił w końcu wieku XIX, spowodowany m.in. uruchomieniem w roku 1899 linii kolejowej, sprzyjał dalszemu rozwojowi miasteczka jako znaczącego już ośrodka turystyczno-wypoczynkowego. Powstało wówczas kilka hoteli, gospód i pensjonatów. Zarówno warownia katedralna, otaczające ją kanonie, jak i miasto często niszczono w licznych wojnach. II wojna światowa szczególnie ciężko doświadczyła miasto. Front przetoczył się dolnym tarasem, dlatego Wzgórze Katedralne poniosło mniejsze straty. Po zakończeniu wojny Frombork po 173 latach powrócił do Polski. W roku 1946, podjęto decyzję o zorganizowaniu Muzeum Mikołaja Kopernika. Muzeum to udostępniono zwiedzającym we wrześniu 1948.
Odbudowa zniszczonego w ponad 80% Fromborka była przedsięwzięciem bardzo poważnym. Wymagała dużych nakładów środków oraz sił. Przy odbudowie Fromborka pomagali harcerze oraz konserwatorzy zabytków. W latach 1966-1973 prowadzono odbudowę Fromborka, w ramach akcji Związku Harcerstwa Polskiego pod kryptonimem "Operacja 1001 Frombork". 2391 instruktorów i harcerzy za swoją nienaganną pracę, trwającą co najmniej trzy turnusy, otrzymało najwyższe wyróżnienie - tytuł Honorowego Obywatela Fromborka.