Несмотря на неоднократные обращения, король Венгрии остался при своем мнении, и тевтонские рыцари были изгнаны из Венгрии, но колонисты, которых они сюда позвали, остались на месте и сохранили свой статус. Это доказывает, что политика Андрея II была направлена не против колонистов — diploma Andreanum уже доказала это раньше, — а против Тевтонского ордена в той мере, в которой последний попытался создать независимое государство на территории королевства. Этого король Венгрии при поддержке своего окружения, в частности сына и наследника принца Белы, в будущем Белы IV, и венгерской Церкви, которая всегда боролась за сохранение собственного авторитета, не мог допустить.

Следует также добавить, что опасность со стороны куманов, бывшая реальностью в 1211 г. и ставшая одной из причин привлечения Тевтонского ордена в Трансильванию, стала менее ощутимой для Венгрии в 1225 г. Куманы перед лицом татарского нашествия охотно обращались в христианство в обмен на защиту со стороны Венгрии, ибо в 1227 г. через два года после изгнания Тевтонского ордена куманский принц Барк и его народ приняли христианство и попросили защиты у короля Венгрии. С тех пор страна куманов присоединилась к королевству. Но перед опасностью со стороны татар куманам пришлось оставить свои земли и искать убежища в Венгрии.

Анекдотичной и бесперспективной на первый взгляд могла бы показаться попытка тевтонских рыцарей обосноваться в Трансильвании, но она тем не менее остается показательной, ибо уже тогда проявились основные черты политики колонизации в том виде, как ее понимал Тевтонский орден. Действительно, в Трансильвании Тевтонский орден попытался создать собственное государство, защищенное целым рядом крепостей и укреплений в стратегически важных точках, — государство, независимое от местного духовенства и находящееся под покровительством папы; орден проводил политику систематического заселения земель, призывая колонистов из Германии, которые по прибытии на место обретали статус свободных людей и получали участок земли, выплачивая лишь годовой налог и неся военную повинность. Этот неудачный опыт в Трансильвании вскоре повторится — на этот раз успешно — несколько лет спустя в Пруссии.

Зимой 1225-1226 гг. делегация во главе с прусским епископом отправилась в Италию, где встретилась с Германом фон Зальца, который в то время находился при дворе Фридриха II. Епископ Конрад обратился к Тевтонскому ордену от имени князя Мазовии с просьбой оказать помощь в борьбе против бесконечных набегов старопруссов, за что князь Конрад пообещал передать ордену Кульмские земли (Кульмерланд), т. е. территорию площадью 3000 км², расположенную в низовьях Вислы, а также все территории, которые будут отвоеваны тевтонцами у пруссов.

Существует мнение, что Герман фон Зальца особого восторга по этому поводу не выразил, ибо печальный опыт, приобретенный орденом в Трансильвании, его настораживал. Герман фон Зальца захотел получить весомые гарантии. Он их получил, сначала от Фридриха, который Золотой буллой Римини в марте 1226 г. дал свое добро и подтвердил передачу земель Кульмерланда, «коль эти земли являются частью империи». Надо сказать, что для императора любая территория, расположенная за Одером, считалась естественным продолжением Священной империи. Булла также гарантировала тевтонским рыцарям передачу земли в собственность и ее неприкосновенность.

По мнению Германа фон Зальца, предоставленных гарантии было недостаточно. Хотя его уговаривали папа и император принять предложение князя Мазовии, великий магистр требовал более подробной информации об истинном положении дел в Пруссии, поэтому он направил туда двух своих сподвижников, которых сопровождали восемнадцать рыцарей. Петр из Дусбурга в своей «Хронике земли Прусской» пишет: «Названный магистр (т. е. Герман фон Зальца) направил брата Конрада фон Лансберга и другого брата ордена к польскому князю, дабы изучить землю Кульм. <…> Когда они прибыли в Польшу… там бесчинствовали пруссы, грабили страну…» Оба брата и их свита, принявшие участие в боях на стороне поляков, были серьезно ранены, и их лечила супруга князя Мазовии, герцогиня Агафия. Немного позже по совету супруги и сыновей Конрад подарил «братьям ордена Кульмскую и Лабаускую земли и вдобавок — все, что отвоюют у пруссов в дальнейшем».

Несмотря на подтверждение передачи ордену земель, Герман фон Зальца все еще сомневался. После годичного размышления он направил князю Мазовии новую делегацию под предводительством командора Филиппа Сальского в сопровождении двух братьев ордена. Герман фон Зальца в то время был занят организацией крестового похода Фридриха II, который уже готов был отправиться в Святую землю. Переговоры тем не менее с князем Мазовии продолжались, и вот хартией от 23 апреля 1228 г. тот подтвердил право ордена на ранее пожалованные концессии. Окончательное решение не было принято, ибо Герман фон Зальца отправился в Святую землю, дабы встретиться там с Фридрихом II, но представители ордена остались при дворе Конрада, чтобы продолжить переговоры. По возвращении Германа фон Зальца в Европу были установлены новые контакты с князем Мазовии. Последний в начале 1230 г. издал новую хартию, согласно которой тевтонским рыцарям уступалась вся территория Кульма со всеми прилагающимися постройками (totium ex integro chelmens territotium cum omnibus suis appendiciis ab eo loco). Следующая хартия, изданная чуть позже, добавила к предыдущим концессиям крепость Нессау и четыре прилегающие к ней деревни.

Окончательный договор между Тевтонским орденом и князем Мазовии, заключенный 30 июня 1230 г. в Крушвице, повторяет основные положения предыдущих договоров и уточняет, что территория Кульма включает также крепость Кульм. Чтобы обезопасить себя, Герман фон Зальца попросил папу, князя Мазовии и его сына Казимира подтвердить условия Крушвицкого договора. Оставалась одна проблема — отношения между орденом и епископом Пруссии Христианом, который владел землями в Кульме, получал с них десятину и взимал различные налоги.

После длительных переговоров между орденом и епископом последний отказался по условиям Рюбенихтского договора (март 1231 г.) от всех земель в Кульмерланде и передал во владение тевтонским рыцарям треть Пруссии.

Начиная с 1230 г., после того как были получены все гарантии от лапы, императора и князя Мазовии, тевтонские рыцари прибыли в Пруссию. Герман фон Зальца направил в качестве магистра земли (Landmeister) одного из своих самых близких сподвижников — Германа Балка родом из Тюрингии. Магистр тут же отправился в путь в сопровождении пяти братьев-рыцарей и сотни воинов, к которым присоединилось подкрепление, прибывшее с севера Германии. Они нашли на этих землях небольшое командорство ордена в Вогесланде на левом берегу Вислы, там был построен несколько лет спустя город Торн. Речь шла о небольшой деревянной крепости, построенной на земле, принадлежащей князю Мазовии, которую он передал ордену в 1226 г. Сразу по прибытии в Пруссию Герман Балк укрепил крепостные сооружения и построил еще одну крепость в Нессау, в нескольких километрах от Фогельзанда. Затем весной 1231 г. Балк и его команда — в общей сложности около тысячи человек — переправились через Вислу и начали систематически отвоевывать земли пруссов. Одержав несколько побед, Балк приступил к строительству крепости на правом берегу Вислы вблизи того места, где епископ христиан построил деревянную башню (Turm); долго считалось, что название города Торнторунь происходит от слова Turm, однако сегодня признано, что Торн следует отожествлять с названием крепости Торн в Святой земле. Этот первый крепостной замок известен под названием Альтторн. Немного позже месторасположение Торна было перенесено на более выгодное в стратегическом плане место, находящееся на несколько километров выше по течению. Новый Торн (Торунь по-польски, Труниа по-латыни) был построен на плато, возвышающемся над рекой, и его стены образовывали в плане пятиугольник; он был защищен крепостью, перестроенной в 1250 г., и мощным замком ордена и окружен высокой стеной. На главной площади города построили церковь Св. Иоанна, позже церковь доминиканцев. В 1232 г. Торн получил юридический статус города. За пределами стены несколько позже возник новый город (Neustadt) — торговый город, который противопоставлялся старому (Altstat), административному и военному. Торн стал первым городом тевтонцев в Пруссии и послужил образцом для последующих городов ордена. Множество крестоносцев под предводительством бурграфа Магдебурского прибыли из северной Германии и Богемии, привлекаемыми выгодными перспективами колонизации восточных земель. Прибытие колонистов было тем более выгодно, что старопруссы постоянно нападали на владения Тевтонского ордена, грабили и убивали население. Для ордена единственным эффективным средством противостояния набегам и оккупации заселенных немецкими колонистами земель стало подчинение себе местного населения.