Il territorio della Prussia Orientale, fino alla conquista dell'Ordine Teutonico, era abitato da tribù baltiche, come i Pomesaniani, Bartiani, Curoniani, Sudiviani, Scaloviani ed altri (che i cronisti tedeschi chiamavano Prussiani), che avevano formato una confederazione di territori tribali.
Prima del 13° secolo i Prussiani avevano ripetutamente aggredito le vicine Polonia, Russia e Danimarca. Ma queste campagne erano sporadiche e non spinsero gli avversari a controllare o a distruggere le tribù prussiane. Solo i polacchi avevano tentato ripetutamente di impadronirsi del territorio per ottenere uno sbocco sul Mar Baltico, ma queste spedizioni non ebbero mai successo, a causa della accanita resistenza dei Prussiani.
La situazione cambiò dopo il 1206, quando Papa Innocenzo III emanò una bolla per la cristianizzazione della Prussia, dando così inizio ad una crociata nel Baltico. Nel 1218 emanò una seconda bolla, con la quale equiparava la crociata in Prussia con le crociate in Palestina.
Nel 1224 il Duca polacco Corrado I di Masovia tentò di sottomettere i prussiani aizzandogli contro i “Cavalieri di Dobrin” ma anch’essi vennero respinti e la controffensiva dei prussiani fu talmente intensa che lo stesso Corrado si vide in pericolo. Il Duca chiese quindi aiuto ai Cavalieri Teutonici perché intervenissero contro le tribù prussiane che vivevano nel territorio e non erano state ancora cristianizzate.
I Cavalieri, in cambio del loro intervento ricevettero in dono la Terra di Chelmno (Kulmerland) ed i territori che avrebbero in seguito conquistato ai vetero-prussiani. Con la Bolla d’oro di Rimini (del marzo 1126) Federico II di Svevia (imperatore del Sacro Romano Impero dal 1220 al 1250) riconosceva all’Ordine Teutonico la sovranità sulle terre conquistate ai vetero-prussiani.
L’Ordine Teutonico si servì di questi documenti come fonte di legittimazione per la conquista della Prussia Orientale, che prese (tra il 1231 e il 1238) la forma di una vera crociata, pur essendo nata dall’interesse dell’Ordine Teutonico a costruire in questi territori un proprio dominio di tipo territoriale. Per amministrare il territorio i Cavalieri Teutonici istituirono uno “Stato Monastico” (tedesco: Ordenstaat).
Nei villaggi abitati dai vetero-prussiani venivano nominati come capovillaggio i convertiti, detestati dagli abitanti, soprattutto perché costringevano con la forza alle corvée i contadini sottomessi. Queste forme di sfruttamento, unite al mancato mantenimento delle promesse in fatto di libertà di culto, provocarono diverse rivolte.
Lo Stato Monastico era diviso geograficamente in dieci aree geografiche che prendevano il nome dalle tribù vetero-prussiane che le abitavano: Pomesania, Pogesania, Varmia, Natangia, Sambia, Bartia, Nadrovia, Sudovia, Galindia, e Scalovia e a tutt’oggi hanno mantenuto i loro nomi.
Per difendere il territorio nella seconda metà del 13° secolo vennero costruiti diversi castelli, come quello di Krantz (Zelenogradsk), Noykuren (Pionersky), Rauschen (Svetlogorsk), Insterburg (Chernyakhovsk) e, nel 1255, Königsberg (Kaliningrad), Marienburg (Malbrok).
Il Castello di Marienburg (Castello di Maria) divenne la sede dell’Ordine
Teutonico dal 1309 al 1457, mentre il castello di Königsberg divenne la
residenza del Gran Maresciallo (capo militare del Cavalieri).
I castelli furono i punti di partenza per la colonizzazione tedesca, in quanto i cavalieri dell’Ordine Teutonico avevano avuto un vivo interesse verso l’insediamento di agricoltori, artigiani e commercianti tedeschi.
L’Ordine teutonico favorì l’afflusso di coloni tedeschi, che assimilarono di fatto la popolazione indigena. Nel 13° e 14° secolo, i coloni provenivano soprattutto dalla Germania meridionale, dalle zone di influenza della Lega Anseatica, dalla Germania centrale e da altre zone di precedenti insediamenti.
Il periodo tra la fine del 14° secolo e l’inizio del 15° secolo può essere considerato come il più fiorente dell'Ordine Teutonico. In questo periodo, l’Ordine massimizzò il suo territorio, l'afflusso di cavalieri crociati dall’Europa gli consentiva una guerra a lungo termine con i principati russi e con lo Stato lituano. Grazie alla sua posizione geografica e la partecipazione delle città prussiane alla Lega Anseatica aumentò il benessere finanziario. In questo periodo la Prussia aveva 85 città, 60 delle quali erano state fondate nel XIV secolo, e 1400 villaggi.
Le politiche espansionistiche dei Cavalieri li portarono in conflitto con il
Regno di Polonia e li coinvolse in numerose guerre, che si conclusero con la
guerra lituano-polacco-teutonica, in cui gli eserciti uniti di Polonia e
Lituania, sconfissero le principali forze militari dell’Ordine Teutonico nella
Battaglia di Tannenberg-Grunwald nel 1410. In questa battaglia, ucciso il Gran
Maestro dell'Ordine Teutonico, Ulrich von Jungingen. Con la battaglia di
Tannenberg-Grunwald, si chiuse l’epopea eroica dell’Ordine dei Cavalieri
Teutonici. L’Ordine riuscì a mantenere la fortezza di Malbork, ma ormai la sua
debolezza era tale che non poteva più costituire un pericolo per i vicini.
Nonostante il fatto che il primo Trattato di Thorn del 1411 fu abbastanza morbido per l'Ordine Teutonico (i Cavalieri perdevano la Samogitiya e la Polonia restituiva all'Ordine le terre prussiane conquistate e rilasciava i Cavalieri catturati), l'Ordine Teutonico perse il suo potere.
La sconfitta definitiva dell’Ordine fu formalizzata nel secondo trattato di Thorn nel 1466 che poneva fine alla guerra dei tredici anni, e costringeva l’Ordine Teutonico a lasciare la Pomerelia sotto il controllo polacco. La Pomerelia, insieme con la Varmia, formò la provincia polacca della “Prussia Reale”. I Cavalieri Teutonici continuavano a controllare quello che restava della Prussia Orientale, ma come vassalli della Polonia.
L’Ordine Teutonico perse definitivamente la Prussia orientale, quando il Gran
Maestro Alberto di Brandeburgo-Ansbach, appartenente alla casata degli
Hohenzollern, si convertì al luteranesimo e secolarizzò il ramo prussiano
dell’Ordine Teutonico nel 1525. Albert ricevette il titolo decolare di Duca di
Prussia, vassallo della corona polacca che si impegnava a fornire assistenza
militare alla Polonia. Convocato dalla Corte Imperiale di Giustizia, Alberto si
rifiutò di apparire, mentre l'Ordine dei Cavalieri Teutonici elesse un altro
Gran Maestro, Walter von Cronberg che, alla Dieta di Augsburg, fu infeudato con
il titolo di Maestro di Prussia, l’Ordine non riprese più il possesso del
territorio.