В 1226 г. Фридрих II подписал буллу, предоставлявшую Ордену свободу действий в Пруссии. Ордену была пожалована Хелминская земля. Орден также получил права на завоевание новых земель на территории Пруссии. Перед началом похода рыцари Ордена подписали с поляками в 1234 г. соглашение, по которому Орден получал во владение Хелминскую землю и все территории, отвоёванные у пруссов.

Великий магистр Тевтонского ордена Герман фон Зальца

Хелминская земля согласно договору становилась временной базой орденских войск и плацдармом для дальнейшего наступления на Пруссию. Однако рыцари имели гораздо более масштабные планы, нежели те, которые они номинально провозглашали перед прибытием в польские земли.

В 1230 г. папа Григорий IX издал буллу, дававшую Тевтонскому ордену право крещения пруссов и закрепления за собой всех завоёванных земель, которые затем формально переходили под контроль и опеку папского престола. В том же году начались активные боевые действия.

Магистр послал в Мазовию авангард, состоящий из 7 рыцарей и 70–100 оруженосцев во главе с Конрадом фон Ландсбергом. Завладев замком Фогельзанг, рыцари, не встретив серьёзного сопротивления, организовали небольшой рейд на язычников, проживавших на другом берегу Вислы. В этом же году в уже отстроенный замок прибыли подкрепления из 20 рыцарей и 200 оруженосцев во главе с Германном фон Балком. В Пруссию были посланы очень ограниченные силы, так как основные орденские войска были задействованы в операциях в Малой Азии и Армении.

Тевтонцы сосредоточились на строительстве приграничных крепостей вдоль берега Вислы. В ранних походах и набегах участвовали главным образом польские, немецкие и померанские крестоносцы с незначительным числом вспомогательных войск, набранных из лояльных пруссов.

Большинство крестоносцев возвращалось домой после очередной кампании, поэтому Орден постоянно нуждался в подкреплениях и свежих силах для проведения дальнейших военных операций. Тевтонцы продвигались вперёд, строя небольшие деревянные форты, обороняемые малочисленными гарнизонами. На восток переселялось множество колонистов из Священной Римской империи, ежегодно основывавших новые города, некоторые из которых получали Кульмское право. Речь идёт о кодексе отношений между городом и сюзереном. Кодекс был подписан 28 декабря 1233 г. в городе Торне, а затем хранился в ратуше города Кульма.

Крестоносцы напали на соседнее племя помезанцев во главе с вождём Пиппином. Выступив из Нешавы, Герман фон Балк с тевтонцами и польскими союзниками двинулся к замку Рогов, удерживаемому пруссами. Местный вождь, владевший городищем и окрестностями, был разбит и попал в плен. Вынужденный для спасения своей жизни пойти на сотрудничество с тевтонцами, он хитростью помог крестоносцам завладеть замком, а затем обманом захватил в плен Пиппина, приходившегося ему шурином. На этом сопротивление пруссов в Хелминской земле было окончательно подавлено.

Тогда же, в 1232 г., крестоносцы основали город Кульм. Тем временем папа римский собрал подкрепления, и на помощь крестоносцам отправился пятитысячный отряд магдебургского бургграфа.

Летом 1233 г. десятитысячное войско крестоносцев вновь выступило в поход, основав крепость Квидзын в Помезании. В зимнем походе 1233–1234 гг. крестоносцев поддержали померанские князья братья Святополк и Самбор.

В решающем сражении на реке Сиргуне тевтонцы наголову разгромили пруссов, во многом благодаря военному опыту князей Святополка и Самбора. Основание крепости Радзынь в 1234 г. ознаменовало собой окончательное закрепление за Орденом земель восточной Помезании. Прусский епископ Христиан заявил свои права на две трети территории завоёванных прусских земель.

Одна треть досталась Ордену. Папский легат Вильгельм Моденский, опасаясь разногласий между христианскими властями, выступил посредником в разделении завоёванных земель. Рыцари получили в итоге две трети территории, но епископ сохранял за собой особые права в этом регионе.

Тевтонцы, помимо всего прочего, добивались включения Добжиньского ордена в состав Тевтонского. В ответ Конрад Мазовецкий потребовал возвращения занятой крестоносцами Добжиньской земли. Рыцари, однако, не торопились уходить. В итоге Конрад перестал оказывать поддержку Ордену.

С санкции папы и плокского епископа тевтонцы присоединили к себе Добжиньский орден буллой 19 апреля 1235 г., однако недовольный Конрад Мазовецкий получил обратно Добжиньский замок. В 1237 г. Тевтонский орден воссоединился с орденом меченосцев, сильно ослабленным в результате страшного поражения, нанесённого ему литовцами в битве при Сауле.

Конрад I Мазовецкий. До 1893 г. Худ. Ян Матейко

Пользуясь поддержкой мейссенского маркграфа Генриха, прибывшего в Пруссию с отрядом в 500 воинов и большими богатствами, крестоносцы активно продвигались вдоль обоих берегов Вислы, покоряя ещё не подчинённые помезанские племена. В 1237 г. тевтонцы начали поход против помезанских племён. Тем временем маркграф, посчитав свой обет выполненным, вернулся обратно, однако оставил крестоносцам корабли и значительные силы, позволившие крестоносцам одержать победу над пруссами. На своём пути крестоносцы выстроили замок Эльбинг.

В 1238–1240 гг. крестоносцы вели войны с племенами вармийцев, бартов и наттангов. В одной из стычек вармийцы разгромили и уничтожили отряд крестоносцев, разорявший окрестности прусской крепости, которую крестоносцы не решались штурмовать в силу своей малочисленности. В ответ на это магистр послал против пруссов большое войско, которое штурмом взяло замок благодаря предательству вождя Кодруна, командовавшего его гарнизоном. Захваченная крепость в 1239 г. была переименована в Балгу. Пруссы во главе с вармийским вождём Пиопсо попытались отбить замок, но безуспешно.

Вскоре рыцари с помощью Брауншвейг-Люнебургского герцога Отто I подчинили своей власти Натангию и Бартию. В октябре 1243 г. папа при участии Вильгельма Моденского разделил завоёванную прусскую землю на Кульмское, Помезанское, Эрменландское и Самландское епископства, хотя земли Самбии ещё не были покорены.

После завоевания западных пруссов к середине 1250-х гг. крестоносцы продолжили продвижение на восток, где столкнулись с прусским племенем самбов, населявшим дикие и слабозаселённые земли Самбии. Многочисленные походы тевтонцев возглавил комтур Христбурга Генрих Штанге. В 1252 г. самбийцы разгромили тевтонцев, а Штанге погиб в бою.

С целью восполнить понесённые крестоносцами потери папа и новый магистр Поппо фон Остерна объявили новый крестовый поход против язычников. Для похода на пруссов были собраны огромные силы, насчитывавшие 60 тысяч воинов.

В Самбию отправились король Чехии Пршемысл Отакар II, бранденбургский маркграф Оттон III, король Германии Рудольф I, оломоуцкий епископ Бруно фон Шауэнбург и многие другие. Объединённые силы крестоносцев нанесли поражение самбам в битве близ замка Рудов. Пруссы, оборонявшие замок, сдались и вскоре приняли крещение.

После победы крестоносцы продолжили завоевание самбийских земель, беспощадно истребляя всех, кто не желал принимать крещение. Были завоёваны волости Кведенов, Вальдов, Кайме и Тапиов. К январю 1255 г. Самбия была завоёвана.

Чтобы закрепиться в покорённой Самбии (Землянде), король Отакар и гроссмейстер ордена Полло фон Остерна построили несколько небольших крепостей. Именно там в 1255 г. была построена деревянная крепость (замок) Кёнигсберг (Королевская гора).

Это одна из версий. Историк Фриц Гаузе утверждает:

«Пребывание крестоносцев было здесь столь непродолжительным – 17 января они были уже снова в Эльбинге, – что Оттокар не основал ни города, ни крепости. И если гохмейстер назвал крепость, строительство которой начали после отступления холодов, в честь своего королевского сподвижника, то это было актом дипломатической вежливости. Таким образом чех стал патроном Кёнигсберга, и город всегда чтил его память.