Quelques années après son arrivée en Pologne⁽¹⁾, l'Ordre Teutonique envahit déjà les terres de la tribu prusse des Warmiens⁽²⁾. Suite à ces invasions, l'évêché de Warmie est créé en 1243⁽³⁾. La gestion du territoire de l'évêché nouvellement constitué est partagé entre l'évêque et le chapitre des chanoines, à raison de 2/3 pour le premier et 1/3 pour les autres. Le territoire de Frombork, où était déjà implanté un gród⁽⁴⁾ prusse, dépendait du chapitre.

Les évêques de Warmie choisissent Braniewo, situé à quelques kilomètres un peu plus au nord-est comme siège de l'évêché et y entament d'abord la construction d'un fort qu'ils transformeront par la suite en château et en même temps, ils commencent la construction de la première cathédrale de Warmie, dédiée à St André l'Apôtre.

Au cours de la deuxième insurrection des Prusses⁽⁵⁾, la ville de Braniewo est détruite et la cathédrale fortement endommagée. L'évêque et le chapitre portent alors leur attention sur le site de Frombork, le trouvant plus propice à la reconstruction de l'évêché et de la cathédrale. En 1274, l'évêque Heinrich I Fleming⁽⁶⁾ déplace officiellement le siège de l'évêché de Braniewo à Frombork, et commence les travaux de construction d'une nouvelle cathédrale.

L'emplacement de cette nouvelle construction est choisi avec soin et est probablement situé à l'endroit ou s'élevait l'ancien gród prusse.
Cet emplacement est situé à l'extrémité nord d'un plateau. A l'ouest et à l'est, l'accès est protégé par un profond ravin, et au nord, sur la rive du Zalew Wiślany⁽⁷⁾, par une falaise abrupte.

Il semble que la première cathédrale ait été construite uniquement en bois. A la fin du 13^ème siècle, elle est complètement entourée par une enceinte fortifiée constituée d'un talus de terre et d'une palissade de bois.
Pour protéger l'accès par le sud, un fossé sec, large et profond est creusé.

Vers 1330, les fortifications de terre sont nivelées, ce qui agrandit le terrain constructible autour de la cathédrale et une nouvelle muraille, en briques cette fois, commence à être construite. Vers la même époque, l'évêque Heinrich Wogenap⁽⁸⁾ fait débuter les travaux de construction de la cathédrale en briques et en pierres. Il est possible qu'au même moment, l'évêque ait décidé de construire un ensemble formé d'une cathédrale accollée à un château, comme le chapitre de Pomésanie l'a fait à Kwidzyn. Ce qui semble être une preuve de cette décision est le fait que dans les sources médiévales latines, le "complexe" de la cathédrale de Frombork est mentionné à plusieurs reprises comme "Castrum Domine Nostrae" (Château de Notre Dame), d'où le nom allemand Frauenburg, polonisé par la suite en Frombork.

La première phase de ce nouveau chantier d'envergure consiste en l'aménagement du plateau autour de la cathédrale et l'érection d'une muraille garnie de plusieurs tours.
L'entrée principale du nouvel ensemble se trouve dans la courtine nord et appelée Porte de la Tour (n°8 sur le plan ci-dessus). La muraille a été construite en briques sur une hauteur de plus de 7m. Dans la partie supérieure du mur, deux rangées de meurtrières sont aménagées et accessibles par le chemin de ronde sur lequel sont installés des hourds⁽⁹⁾.

La partie la plus courte des remparts est le côté ouest. On y trouve deux grandes tours d'angles (n°3 et 6 sur le plan ci-dessus). Entre ces deux tours, une porte est aménagée dans la muraille et surmontée d'un élément défensif (n°4 sur le plan ci-dessus). Cette porte est appelée "Porta Minor". Cette porte a été reconstruite et restaurée à plusieurs reprises, surtout au cours des 19^ème et 20^ème siècles.

Le côté le plus long des remparts est la partie sud. L'élément le plus imposant de ce rempart sud, est la tour d'angle située au sud-ouest des remparts. Cette tout est appellée "Magna Turris"(n°3 sur le plan ci-dessus). Construite dès le début du 15^ème siècle, elle longtemps été un point clé des défenses de la forteresse. Cette tour a été amménagée pour pouvoir abriter des pièces d'artillerie lourdes et aussi des armes plus légères.

La seconde phase des travaux d'agrandissement de l'ensemble a débuté au 15^ème siècle avec le percement dans le rempart sud, en face de la cathédrale, d'une nouvelle porte, qui est rapidement devenue la porte principale de la forteresse(n°1 sur le plan ci-dessus). Cette porte, dès l'origine, a été entourée de deux tours semi cylindrique reliées par une courtine qui formait un ensemble de défense massif et appelé "Porta Major". Le fossé se trouvant devant les remparts sud a été élargi et approfondi.
Au 16^ème siècle, une barbacane est ajoutée devant cette porte d'entrée, au dessus du fossé, ajoutant ainsi un nouvel élément défensif.

La partie orientale est la plus vieille et date de la première moitié du 14^ème siècle. Un ensemble de bâtiments est accolé à ce mur, avec du nord au sud : la salle du chapitre, lieu de réunion des chanoines ; le palais de l'évêque et la maison du doyen(n°12, 13 et 14 sur le plan ci-dessus). Ces deux derniers bâtiments formant ce qu'il est convenu d'appeler "le château".
Au centre de ce mur, une tour saillante cylindrique a été construite vers 1536, et avait à l'origine trois étages. Au 17^ème siècle, elle a été transformée en cuisine.

A la fin de la première phase des travaux d'aménagements, soit vers la fin du 14^ème siècle, la forteresse de Frombork n'était pas très menacées par les raids des tribus Prusses ni par les Lituaniens, qui rencontraient déjà plusieurs châteaux teutoniques dans les régions de Sambie, Warmie du sud, Natangie,...⁽⁶⁾

La première menace sérieuse pour les évêques de Warmie est arrivée au début du 15^ème siècle, avec les guerres entre l'Ordre Teutonique et la Pologne. Après la défaite des Teutoniques à Grunwald⁽¹⁰⁾ et avec l'accord de Henry Vogelsang⁽¹¹⁾, évêque de Warmie, le chapitre offre la forteresse au roi de Pologne sans combat.

Au début de la guerre de Treize Ans⁽¹²⁾, l'évêque de Warmie et les chanoines, théoriquement indépendants, se sont alliés à l'Ordre Teutonique. Mais, le 14 février 1454, impressionné par un discours et un resssentiment anti-germanique grandissant, le chapitre décide de rejoindre l'Alliance Prussienne⁽¹³⁾. L'évêque Franz Kuhschmalz⁽¹⁴⁾ n'accepte pas cette décision du chapitre et la dénonce à l'Ordre Teutonique dont les troupes brûlent la ville le 10 décembre de la même année. Pour sauver la cathédrale et les batiments de l'évêché, le chapitre des chanoines est obligé de verser une forte somme d'argent à l'Ordre. Infiltré par des éléments pro-germaniques, le chapitre trahi l'Alliance Prusienne ainsi que le roi de Pologne Casimir IV Jagellon en 1455.
Alors que les Teutoniques occupent les villes de Olsztyn et Reszel, les premières troupes de l'Alliance Prussienne arrivent devant Frombork, investissent la forteresse, arrêtent les chanoines et brûlent les bâtiments de l'évêché. Des mercenaires tchèques quant à eux pillent la cathédrale et en détruisent les autels.
A partir de ce moment, l'Alliance Prussienne installe une garnison permanente dans la forteresse pour couper la liaison entre les deux grandes forteresses teutoniques de Kaliningrad (Königsberg) et de Malbork.

En 1456, un groupe de mercenaires teutoniques sous le commandement de Volkeld Roder et dirigé par un chanoine de Warmie, Bartholomew Liebenwalde, réussit à tromper la vigilance de la garnison et à pénétrer dans la forteresse. Ces mercenaires font prisonniers 22 soldats tchèques et se retirent immédiatement de la forteresse qui est récupérée par des mercenaires polonais.

Une nouvelle attaque a eu lieu cinq ans plus tard à Frombork. En Septembre 1461, l'évêque de Warmie, Paul Stange von Legendorf⁽¹⁵⁾, allié aux Teutoniques, assiège la forteresse. Pour compléter son armée et faire un blocus complet de la forteresse, il réquisitionne plusieurs centaines de paysans de Warmie ainsi que les citadins de Braniewo. Ce siège, qui a duré 3 semaines, a pris fin suite à une attaque de l'armée polonaise qui a presque anéanti l'ensemble des assiégeants.

En juillet 1462, les Teutoniques essayent pour la dernière fois de récupérer Frombork. La forteresse est assiégée par 3000 hommes commandés par Ludwig von Erlichshausen⁽¹⁶⁾, le Grand Maître de l'Ordre en personne. Malgré la destruction d'une grande partie des murs, l'armée teutonique doit se retirer en apprenant l'arrivée imminente d'une importante armée polonaise.

Actuellement, la forteresse est un musée, tandis que la cathédrale est toujours utilisée pour les offices religieux et est également toujours le siège de l'évêché de la région. Hormis la visite des éléments du château-fort, on peut également visiter une importante exposition dédiée à Nicolas Copernic, qui a été l'un des hôtes les plus célèbres de l'endroit. La Grande tour octogonale lui servant de plate-forme d'observation. Son tombeau a été récement découvert dans la cathédrale.