W latach 1225-1226 książę Konrad Mazowiecki prowadził rozmowy z zakonem krzyżackim. Oferował rycerzom lenno w postaci ziemi Chełmińskiej, a w zamian prosił o ochronę swojej granicy z pogańskimi Prusami. Konradowi Mazowieckiemu udało się dobić targu z Krzyżakami. Nie wiedział, że zakonnicy mają wobec jego ziem, a przede wszystkim wobec Prus, własne tajne plany kolonizacyjne. Tymczasem Wielki Mistrz Hermann von Salza wystarał się u cesarza Fryderyka II o tak zwaną Złotą bullę z Rimini – dokument wydany rzekomo w 1226 roku nadawał Krzyżakom prawa do wszelkich ziem, jakie zdobędą w Prusach. Cesarz wydał go mieniąc się seniorem zakonu, a także zupełnie bezpodstawnie seniorem Polski.
Dziś historycy uważają, że bulla naprawdę powstała dopiero w 1234 roku i została antydatowana. Zakonnicy postarali się też o nadania u papieża, ten ogłosił Prusy własnością św. Piotra i uznał za swoje lenno.
Pierwszych braci zakonnych, dwóch rycerzy i kilkunastu służebnych przysłał Hermann von Salza do ziemi Chełmińskiej w 1228 roku, następni rycerze przybyli dwa lata później. Niewielki oddzialik krzyżacki dowodzony przez Hermana Balka rozpoczął działania wojenne posuwając się wzdłuż Wisły, przekroczył ją i zbudował mały gród, którego strażnica, jak głosi legenda podtrzymywana przez samych Krzyżaków, znajdowała się na gałęziach olbrzymiego dębu. Były to początki warowni w Toruniu. W następnych latach powstawały kolejne zamki pozwalające na kontrolę podbitych terenów i stanowiące bazę dla dalszych wypadów: Chełmno, Kwidzyn, Elbląg.
Prusowie ponieśli klęskę w walce z Zakonem, podbój ich kraju zakończył się około 1238 roku i od tej pory Krzyżacy zaczęli koncertować uwagę na ziemiach Sambii i Żmudzi, a także Litwy i Polski. Po upadku oblężonej Akki, Krzyżacy na krótko zagościli w Wenecji, w 1308 roku Wielki Mistrz Zygfryd von Feuchtwangen przeniósł stolicę państwa zakonnego z Wenecji do Malborka. Gdy słabło państwo Jerozolimskie rosła pruska potęga zakonu.