В скором времени жители Вармии, Натангии и Бартии, дабы избежать поголовного уничтожения, вынуждены были покориться и принять католическое вероисповедание. Чтобы закрепить эту победу, началось спешное строительство замков: Кройцбурга в Натангии, Бартенштейна, Резеля и Висемберга в Бартии, Брунсберга и Хейлзберга в Вармии.
Местные земли были поделены между немецкими дворянами, которые изъявили желание поселиться в Пруссии на основе ленной службы. Местную молодежь высылали в Германию, где из них воспитывали проповедников христианства.
В 1237 году к Тевтонскому ордену присоединился орден Христа. Членов ордена Христа по изображению меча на плащах называли также меченосцами. Это рыцарское объединение более известно как Ливонский орден. В тот период меченосцы переживали трудные времена. Они непрерывно воевали с русинами, ливами, курами, эстами, семигалами и в то же время конфликтовали с рижским архибискупом.
Орден меченосцев занимал в Ливонии довольно скромное место — из всех завоеванных земель он получал только третью часть. Две остальные части получал местный архиепископ. Объединением с Тевтонским орденом меченосцы надеялись поправить свое положение в Прибалтике. Объединение было ускорено тяжелым поражением, которое нанесли меченосцам литвины под командованием князя Миндовга в 1236 году. В том сражении погиб магистр меченосцев.
Ливонским провинциальным магистром был назначен неутомимый завоеватель Пруссии Герман Балк. Некоторое время он также совмещал и функции прусского ландмейстера. В 1239 году умер Герман фон Зальца — выдающийся деятель Тевтонского ордена, создавший основу построения будущей орденской державы.
Тевтонские рыцари принимали участие в войне с татаро-монголами в 1240—1241 годах, однако неудачно. Татары наголову разгромили объединенные христианские войска в битве под Лагницей в 1241 году. В этом сражении был тяжело ранен прусский ландмаршал.
Вскоре в союз против Тевтонского ордена с пруссами вступил поморский князь Святополк. Он первый среди славянских правителей понял, что после покорения пруссов придет очередь соседних христианских земель. После непродолжительной, но кровопролитной войны тевтонцы с помощью польских князей победили Святополка.
Согласно договору 1243 года Святополк обязался помогать крестоносцам во всех войнах с неверными. Однако спустя непродолжительное время Святополк объединился с пруссами Судовии, опустошил Хелминскую землю и разгромил тевтонское войско. В этой битве погиб прусский маршал.
Святополк потребовал вернуть сына, который находился в руках крестоносцев как заложник верности отца. Рыцари отказались это сделать и призвали поморского князя покориться ордену. Святополк построил на острове посреди Вислы замок Зантырь, перекрыв этим крестоносцам водный путь.
В ходе новой войны с поморами и пруссами тевтонцы, с помощью крестоносцев из Германии и Польши, вновь одержали верх. В 1246 году Святополк был вынужден заключить новый мир. Он обязался порвать отношения с пруссами, помогать тевтонцам в войне с язычниками и оставить родного сына в заложниках.
Однако вскоре Святополк вновь поднял восстание против крестоносцев. И лишь в 1248 году, окончательно исчерпав свои силы, Святополк при посредничестве папского легата заключил мирный договор с крестоносцами.
С помощью того же легата и при его посредничестве 7 февраля 1249 года крестоносцы заключили соглашение с новокрещеными пруссами из Померании, Вармии и Натангии. Местные христиане получили определенные права. Они имели право самостоятельно покупать и продавать землю, распоряжаться движимым имуществом и вступать в брак.
Со своей стороны пруссы гарантировали придерживаться христианства, сохранять верность ордену и не сжигать своих мертвецов. Однако пруссов-христиан было еще очень мало и они нетвердо придерживались принятых обязательств. В скором времени они объединились с язычниками, устроили засаду на дороге между рыцарскими замками и уничтожили крупный отряд крестоносцев.
Ордену вновь оказали поддержку европейские рыцари, которые прибыли в Пруссию в 1257 году в большом количестве. С помощью этого крупного воинского контингента были покорены Померания, Вармия, Натангия, Бартия и Галиндия. Местные жители были вынуждены принять христианство.
В 1252 году Тевтонский орден завоевал Поморье. Спустя год крестоносцы заключили новый мир со Святополком на условиях, что в случае его нового выступления против ордена, он будет лишен города Гданьска.
С помощью западноевропейских рыцарей тевтонцы покорили в 1254 года Самбию. В 1255 году был основан Кенигсберг, который впоследствии стал одним из крупнейших портов Балтийского моря. Однако в 1259 году объединенное войско Тевтонского и Ливонского орденов вместе с датскими рыцарями потерпели сокрушительное поражение от литвинов под командованием князя Миндовга в битве при озере Дурбе.
Сразу же усилилось сопротивление пруссов. В том же году орден меченосцев возобновил боевые действия против местных племен Восточной Прибалтики, а также предпринял опустошительные рейды в направлении русских городов Пскова и Новгорода.
В сопротивлении с неверными крестоносцы не считали обязательным придерживаться норм христианской морали. В 1260 году орденский прокуратор Вармии и Натангии Вальрод Мирабилис пригласил на пир в замок Ленценберг местных прусских аристократов. Подобные собрания случались уже не раз, поэтому пруссы пришли, не предприняв никаких мер безопасности.
В самый разгар пиршества по приказу прокуратора в помещении, где собрались прусские аристократы, были заколочены двери и окна, а сам дом подожжен. Никто не сумел вырваться из огня. В ответ на это злодеяние во всех прусских землях вспыхнуло восстание.
Верность крестоносцам сохранили только Хелминская земля и Помезания. Они были почти целиком заселены колонистами-христианами. В восстании приняли участие самбийские, натангийские, варминские, бартийские и погезамские пруссы. Размах восстания в сентябре 1260 года был настолько мощным, что орденское государство едва не рухнуло.
В ряде случаев повстанческие отряды возглавили пруссы, которых крестоносцы в младенческом возрасте отправили в Германию для воспитания в христианском духе. Те христиане, которые не успели укрыться в замках, были убиты прямо в своих колониях. Повстанцы сжигали костелы и убивали священников.
Как сообщал орденский хронист, одного священника пруссы положили головой между двух бревен и, сжимая их, постепенно задушили, говоря с издевкой, что не смеют проливать кровь такой святой особы. Некоторых пленных пруссы приносили в жертву своим богам. Так, в полном вооружении, на коне был живьем сожжен один из пленных рыцарей.
Рыцарские гарнизоны были осаждены в замках. Дважды из Германии к ним на помощь приходило подкрепление, но оба раза орденское войско было разгромлено пруссами. Повстанцы успешно осаждали такие крупные замки, как Кройцбург и Бартенштейн. Гарнизон Кройцбурга оставил замок и спасался бегством. Однако пруссы догнали рыцарский отряд и поголовно уничтожили.
Та же участь едва не постигла гарнизон Бартенштейна. Однако на этот раз крестоносцы пошли на хитрость. Весь рыцарский отряд ночью тихо вышел из замка, оставив там лишь старого тевтонца, который регулярно звонил в колокол церкви, как бы созывая братьев на богослужение. Пруссы не сразу заметили этот обман.
Однако осада Кенигсберга окончилась неудачно. Долго сумел продержаться замок Хейлсберг в Вармии, несмотря на многочисленные штурмы и обстрелы из осадных орудий. В конце концов, гарнизон Хей-лсберга сумел прорвать кольцо блокады и укрыться в замке Эльбланг. Вместе с собой они привели 12прусских заложников. Пруссов ослепили и отпустили «на все четыре стороны».
Тем временем ожесточение с обеих сторон нарастало. Ландмейстер Эльбланга узнав, что два рыцаря вошли в тайный сговор с осаждавшими, приказал живьем сжечь предателей. Если бы казненные были язычниками, то этот поступок не вызвал бы возмущения среди прочих крестоносцев. Однако за чрезмерную жестокость по отношению к христианам ландмейстер был лишен должности.