Dwaj prawdopodobnie ludzie zwrócili uwagę Konrada Mazowieckiego na krzyżaków jako zakon rycerski odpowiedni do walki z Prusami — do osłonięcia Mazowsza i Kujaw przed najazdami oraz podbojem pogan dla księcia mazowieckiego. Jednym z nich był biskup płocki Gunter, mający rodzinne powiązania z Turyngią, gdzie krzyżacy byli popularni i posiadali domy klasztorne. Drugim był książę wrocławski Henryk Brodaty, uczestnik krucjat przeciw Prusom, spokrewniony poprzez żonę, św. Jadwigę, z książętami niemieckimi. Już w 1224 roku ofiarował on krzyżakom wieś na Śląsku.

Kontakt z władzami zakonu krzyżackiego nawiązał Konrad Mazowiecki zapewne już w roku 1225. Rozpoczęła się wówczas gra dyplomatyczna — pisał historyk Stanisław Zachorowski — w której obie strony miały własne cele, a w której oczywiście trudno było Mazowszanom sprostać takiemu dyplomacie, jakim był ówczesny wielki mistrz zakonu Herman von Salza, jeden z głównych negocjatorów Fryderyka II w jego walkach z papieżem.

Konrad Mazowiecki i jego doradcy oraz współpracownicy uważali z pewnością, iż osadzenie krzyżaków na pograniczu pruskim odbywa się na tych samych zasadach, co fundacje klasztorów innych zakonów. W zamian za walkę z Prusami — i realizację mazowieckich planów podboju Prus — krzyżacy otrzymają dobra ziemskie w postaci Ziemi Chełmińskiej i jakieś ziemie na pograniczu Prus, które mieli podbić dla księcia. Były to z pewnością posiadłości bardziej rozległe niż otrzymywały zwykle inne zakony. Ale i zadania krzyżaków były większe i wymagały lepszej podstawy materialnej działań. Konrad oczywiście chciał zachować nad tymi obszarami wszelkie prawa wynikające z jego prerogatyw książęcych. Krzyżacy tymczasem chcieli utworzyć nad Bałtykiem autonomiczne państwo zakonne i plan ten realizowali stopniowo.

Już po pierwszych rokowaniach z Konradem wielki mistrz Herman von Salza uzyskał, w marcu 1226 roku, potwierdzenie przez cesarza Fryderyka II ogólnikowo zapewne sformułowanych nadań księcia mazowieckiego. Cesarz w dokumencie tym — zwanym przez historyków niemieckich „złotą bullą" z Rimini — korzystając ze swych uprawnień do dysponowania ziemiami pogańskimi przekazał krzyżakom Prusy i przyznał wielkiemu mistrzowi rozmaite prawa władcze — podobne do tych, jakie posiadali książęta Rzeszy. Przywilej cesarski z roku 1226 nie miał jeszcze wówczas żadnego znaczenia praktycznego. Krzyżacy przystąpili do podboju Prus kilka lat później. Był jednak ten przywilej programem i kierunkiem działań krzyżackich w przyszłości.

Dwa lata później — wiosną 1228 roku — przybyli do Konrada Mazowieckiego posłowie krzyżaccy i uzyskali od księcia dokument nadający zakonowi oficjalnie Ziemię Chełmińską i jedną wieś na Kujawach. Biskup Chrystian zaś przekazał im dziesięciny z dóbr chełmińskich. Kolejny dokument Konrada Mazowieckiego dla krzyżaków (z 1230) potwierdził te nadania. Zakon obiecywał w zamian Konradowi pomoc w walce z poganami. Wszystko to zatwierdził w tymże roku (1230) papież.

Kolejnym etapem zabiegów dyplomatycznych krzyżaków były rokowania z biskupem Chrystianem, jako posiadaczem dóbr w Ziemi Chełmińskiej i jako przedstawicielem papiestwa na terenie Prus. Bez zezwolenia Chrystiana żadne wojsko krzyżowe, również zakonne, nie mogło wkroczyć do Prus — gwarantowały to przywileje papieskie. Rokowania krzyżaków z Chrystianem dotyczyły Ziemi Chełmińskiej i działań w Prusach. Ich rezultatem było przekazanie krzyżakom (1230) przez Chrystiana wszystkich jego dóbr (poza pewnymi majątkami) w Ziemi Chełmińskiej za zbrojną obronę schrystianizowanych Prusów przed napadami pogan. W roku następnym zaś (1231) krzyżacy zawarli z biskupem Chrystianem kolejną umowę. Dotyczyła ona tym razem Prus, których panem — z upoważnienia papieskiego — uważał się Chrystian; zdobyte w Prusach obszary miały być podzielone w ten sposób, że trzecia ich część wraz ze wszystkimi uprawnieniami władczymi przypaść miała krzyżakom. W umowie tej podkreślano nadrzędną rolę biskupa Chrystiana.

Niedługo potem sytuacja zmieniła na korzyść zakonu krzyżackiego: oto około roku 1233 biskup Chrystian, prowadząc akcję misyjną wzdłuż Mierzei Wiślanej, został uwięziony przez Prusów na terenie Sambii. Przebywał w niewoli pruskiej aż do roku 1238. Krzyżacy nie starali się o uwolnienie biskupa z rąk Prusów. Przeciwnie, skorzystali z okazji, aby umocnić swą pozycję prawnopolityczną w Prusach.

Na ten okres przypada zapewne sporządzenie rzekomego przywileju Konrada Mazowieckiego, wydanego jakoby w Kruszwicy (tzw. „przywileju kruszwickiego"). Kopia jego została wpisana do regestów kancelarii papieskiej, a rzekomy oryginał zaginął. Ów „przywilej" Konrada Mazowieckiego nadawał zakonowi władzę zwierzchniczą nad Ziemią Chełmińską i wszystkimi zdobyczami w Prusach. Między historykami polskimi a niemieckimi toczyła się przed blisko stu laty dyskusja na temat autentyczności tego dokumentu Konrada Mazowieckiego i pozostałych nadań dla krzyżaków w Prusach. Brak oryginału, forma dokumentu i zakres nadań — wszystko to wskazuje, iż ów dokument był fałszerstwem kancelarii cesarskiej. Razem z innymi aktami tworzył zbiór dokumentów, będących podstawą państwa krzyżackiego w Prusach.

W papieskiej bulli protekcyjnej z 1234 roku Grzegorz IX uznał podbite już przez krzyżaków obszary Prus i przyszłe ich zdobycze w tym kraju za własność papiestwa, i nadał je zakonowi krzyżackiemu w wieczyste posiadanie. W ten sposób namiestnikiem papieskim w Prusach stały się władze zakonu krzyżackiego. Bulla Grzegorza IX tworzyła zatem autonomiczne państwo zakonne — krzyżackie w Prusach. Dwa lata później (1236) polecił papież swemu legatowi, Wilhelmowi z Modeny, podzielić Prusy na diecezje i utworzone tak biskupstwa pruskie obsadzić dominikanami. Było to wyeliminowanie z Prus Chrystiana i misji cysterskiej. Chrystian po uwolnieniu z niewoli pruskiej (1238) na próżno próbował jeszcze ratować swe prawa i stanowisko w Prusach. W roku 1243 papież Innocenty IV nadał Prusy w lenno wielkiemu mistrzowi krzyżackiemu Gerardowi von Maleberg. Akt ten potwierdzał i utrwalał autonomiczne państwo krzyżackie w Prusach. W tymże roku utworzono cztery diecezje pruskie: chełmińską, pomezańską, warmińską i sambijską; jedną z nich miał sobie wybrać Chrystian. Jednakże niedługo potem biskup zmarł (1245).

Znamienne są te zabiegi i troska krzyżaków o zdobycie pisemnych potwierdzeń nadań i przywilejów. Doceniali oni znaczenie prawne aktu pisanego — dokumentu. Książę polski i biskup pruski w wystawianych dla krzyżaków dokumentach dokładnie określali swe zobowiązania. W zamian nie otrzymali żadnych dokumentów określających zobowiązania krzyżaków. W dokumentach Konrada i Chrystiana dla zakonu jedynie ogólnie są sformułowane obowiązki krzyżaków wobec księcia i biskupa.

Historycy niejednokrotnie zastanawiali się komu zawdzięczali krzyżacy utworzenie państwa zakonnego w Prusach? Odpowiedź na to pytanie nie jest prosta. Na pogranicze polsko-pruskie wezwał krzyżaków książę Konrad Mazowiecki za radą i namową biskupa Chrystiana. Nie ulega jednak wątpliwości, że decyzja ta musiała być poparta przez możnych mazowieckich i kujawskich, tak duchownych jak i świeckich. Konrad i Chrystian uważali, że przy pomocy krzyżaków powstrzymają pogan i opanują całe Prusy. Natomiast wielki mistrz Herman von Salza, wraz z dostojnikami zakonu, dążyli do zbudowania autonomicznego państwa krzyżackiego w Prusach. Popierał ich długoletni legat papieski w krajach Europy Środkowej i północnej, Wilhelm z Modeny. Uznał on krzyżackie państwo zakonne za najlepszą ochronę akcji misyjnej nad Bałtykiem.

Około roku 1228 przybyli do Polski pierwsi krzyżacy: dwóch rycerzy zakonnych i kilkunastu zapewne służby. Kolejna, większa już grupa krzyżaków przybyła nad Wisłę w roku 1230, dowodzona przez Hermana Balka, późniejszego mistrza krajowego Prus i Inflant. Grupa ta liczyła siedmiu rycerzy-zakonników oraz wielu giermków i koni — jak pisał sto lat później kronikarz krzyżacki Piotr z Dusburga. Oblicza się zwykle, iż w tym czasie (tj. XIII—XIV wieku) na jednego rycerza przypadało około 10 giermków i pachołków. Oddział krzyżacki Hermana Balka wynosił zatem około 70 osób.

Zdumienie budzi fakt, że tak niewielka grupa ludzi (jeśli nawet została po r. 1230 powiększona) zdołała w okresie niecałych 10 lat (od r. 1233 lub 1234 do około 1240 r.) tak wiele osiągnąć: krzyżacy podbili w tym czasie całe północno-zachodnie Prusy i dotarli — posuwając się wzdłuż wybrzeża morskiego — aż do Sambii. Pod ich władzą znalazły się plemiona Pomezanów, Pogezanów, Warmów, Natangów i Bartów.

Sukcesy krzyżaków to wynik ich lepszego uzbrojenia, organizacji, kwalifikacji bojowych sił zbrojnych oraz umiejętnej taktyki i dobrego planu podboju. Podbój ułatwiała im również słabość polityczna Prusów, brak zbiorowego oporu i zorganizowanych działań militarnych. Ważniejszym jednak czynnikiem sukcesów krzyżackich była stała pomoc militarna rycerstwa niemieckiego, przychylność dla ich akcji w Prusach cesarza i papieża, pomoc książąt niemieckich, poparcie kupców Lubeki, Bremy i innych miast północno-niemieckich. Papieskie bulle wzywały rycerstwo chrześcijańskiej Europy do wsparcia akcji krzyżaków w Prusach. Zaś starania wielkiego mistrza Hermana von Salza i jego wpływy na dworze cesarskim oraz wśród książąt niemieckich sprawiły, iż papieskie wezwania krucjatowe zaowocowały trzema wyprawami krzyżowymi do Prus — w roku 1233/34 lub 1234/35, 1236 i 1239/40 r. W pierwszej fazie podboju Prus pomoc zbrojna i darowizny książąt polskich na rzecz zakonu — były bardzo ważne.

Wspomnieć należy również o taktyce podboju. Krzyżacy zdobywali ziemie pruskie wzdłuż szlaków wodnych — najpierw z biegiem Wisły do morza, następnie wzdłuż Mierzei Wiślanej do Półwyspu Sambijskiego. Końcowym etapem podboju było opanowanie środkowej części kraju. Panowanie nad szlakiem wodnym Wisły, Nogatu i Mierzei Wiślanej pozwoliło krzyżakom utrzymywać stały kontakt między zajętymi przez nich częściami kraju i zbudowanymi tam warownymi grodami. Drogą wodną łatwo było zaopatrywać grody w żywność i uzupełniać załogę. Pozwoliło to ponadto na uzyskanie stałego i bezpośredniego połączenia morskiego — niezależnego od książąt polskich — z Niemcami: z niemieckimi książętami i rycerstwem oraz z miastami.

Elementem taktyki podboju było także zakładanie na zdobytych ziemiach obozów warownych, grodów-zamków. Budowali je krzyżacy początkowo jako grody drewniano-ziemne (na wzór polski i pruski), potem kamienno-ceglane. Obsadzono je stałą załogą, złożoną z braci zakonnych i żołnierzy krzyżackich. Owe grody-zamki pozwalały na kontrolę i obronę przyległych obszarów, a przy wielkich wyprawach stanowiły bazę wojsk krzyżowców. Podbój kraju synchronizowano z przybyciem do Prus większych grup krzyżowców.

Osadnictwo na zajętych terenach krzyżacy rozpoczęli od Ziemi Chełmińskiej. Już w roku 1233 udzielili przybywającym z Niemiec i Śląska osadnikom tak zwanego prawa chełmińskiego (przywileju lokacyjnego chełmińskiego). Na jego podstawie osady kupców i rzemieślników przy grodach krzyżackich otrzymały samorząd miejski. Później było ono podstawą prawa miejskiego większości miast pruskich, a także podstawą prawa ziemskiego obowiązującego przede wszystkim ludność niemiecką. Ruch osadniczy w Prusach — dzięki sprzyjającej polityce zakonu — objął z czasem także rycerstwo i chłopów. Nowi osadnicy przybywali z ziem sąsiednich — Niemiec głównie, ale również z Polski i Litwy.

A oto krótki przegląd początkowych etapów podboju ziem pruskich. Krzyżacki oddział Hermana Balka przekroczył w roku 1231 Wisłę i założył gród w Toruniu. W roku następnym (1232) krzyżacy opanowali i odbudowali Chełmno, naczelny gród tej ziemi. Następnym celem krzyżackiego podboju była rdzennie pruska Pomezania. Posuwając się wzdłuż Wisły zbudowali krzyżacy, wiosną roku 1233, grodek, zwany Wyspą Marii (Insula S. Mariae, po niem. Marienwerder). Przeniesiono go później na wysoki brzeg Wisły i umocniono, zaś pod grodem założona pierwsze w Prusach miasto — Kwidzyn. Rycerzy zakonnych wspomagał wówczas oddział krzyżowców niemieckich prowadzony przez burgrabiego magdeburskiego Burcharda, hrabiego Kwerfurtu. Pochodził on z tego samego rodu co św. Bruno z Kwerfurtu, misjonarz Prusów lub Jaćwięgów w czasach Bolesława Chrobrego. Burchard z Kwerfurtu był pierwszym znanym z imienia krzyżowcem, który pomagał zakonowi w walce z Prusami.

Może jesienią 1233 lub rok później (zimą 1234/35 r.) — jak dowiódł tego G. Labuda — zorganizowana została pierwsza wielka wyprawa krzyżowa do Prus. Wzięli w niej udział również książęta polscy z rycerstwem: Konrad książę mazowiecki z synem Kazimierzem Kujawskim, Henryk Brodaty książę wrocławski i krakowski, Władysław Odonic książę wielkopolski i dwaj książęta pomorscy — Świętopełk z bratem Samborem. W bitwie nad rzeką Dzierzgonią (Sirgune) Prusowie pomezariscy zostali pobici przez siły polsko-niemieckie. Według kronikarza krzyżackiego Piotra z Dusburga w bitwie zginęło ponad 5 000 Prusów.

W okolicach Kwidzynia widoczne są też pierwsze ślady rycerskiego osadnictwa niemieckiego w Prusach. Oto w styczniu 1236 r. — i w latach następnych — rycerz saksoński Dytrych von Diepenau otrzymał nadania ziemskie. A w zamian za to zobowiązał się do płacenia czynszu i pełnienia służby rycerskiej pod rozkazami krzyżaków.

Podbój Pomezanii zakończyli krzyżacy w roku 1236 z pomocą wielkiej grupy krzyżowców, która przybyła do Prus pod wodzą margrabiego Miśni, Henryka Wspaniałego. Pruskie grody Pomezanii zostały zdobyte a ludność zmuszona do uznania władzy zakonu krzyżackiego. Zawarta wówczas ugoda, regulująca stosunek ludności pomezańskiej do krzyżaków, stała się wzorem dla podobnych umów z mieszkańcami innych podbijanych przez krzyżaków ziem pruskich.

W roku 1237 ruszyli krzyżacy na podbój Pogezanii. Zbudowali tu niedaleko morza nowy gród, Elbląg. Niebawem powstała przy grodzie osada miejska założona przez mieszczan lubeckich i miśnieńskich, którzy wprowadzili tu miejskie prawo Lubeki. Elbląg stał się krzyżacką bazą militarną do podboju kolejnych terytoriów pruskich. Opór Prusów krzyżacy złamali przy pomocy nowych posiłków krzyżowców niemieckich — w sile około 700 zbrojnych — których przyprowadził do Prus drogą morską w roku 1239 książę Brunszwiku Otto Dziecię, wnuk księcia saskiego Henryka Lwa. Rok walk rycerzy zakonnych i krzyżowców z Prusami doprowadził do ujarzmienia Warmów i sąsiednich plemion pruskich — Natangów i Bartów.

W ten sposób rok po śmierci wielkiego mistrza Hermana von Salza (zm. 1239) większość ziem pruskich znalazła się pod panowaniem krzyżackim. Rycerze zakonni dotarli do dolnej Pregoły i do dzisiejszej krainy wielkich jezior mazurskich. Następnym celem była Sambia. Podbój Sambii miał otworzyć krzyżakom drogę lądową do Inflant.