Спускаясь по течению Вислы, Адальберт и его сподвижники достигли Данцигского залива и добрались в 997 г. до Самбинских (Самлаидских) земель, самых богатых земель пруссов, которыми правил griwe. Там они увидели священный дуб, у подножия которого приносили в жертву богам пленных. Адальберт и прибывшие с ним монахи попытались обратить в христианство местное население. Но это закончилось для них плохо. Смелый до безумия, Адальберт отважился срубить священный дуб и во время богослужения в этом священном месте, запретном для непосвященных, был пронзен стрелами пруссов, возмущенных невиданным доселе кощунством. Монахи привезли его тело в Гнездно — религиозную метрополию поляков, где Адальберта и похоронили. Через несколько лет, в 1008 г., монах-бенедиктинец Бруно, родом из Керфурта, поплатился жизнью при аналогичной попытке. После этого к вопросу об обращении в христианство пруссов не возвращались, довольствуясь польской защитой от грабительских вторжений пруссов.

Серьезные попытки обращения в христианство начали предприниматься лишь во второй половине XII столетия, и не по отношению к пруссам, считавшимся слишком опасными, но по отношению к ливонцам, с которыми с 1160 г. торговцы Любека поддерживали тесные отношения. В 1180 г. монах-августинец из епархии Бремена Мейнхард обосновался на острове Готланд. Оттуда в 1184 г. в сопровождении нескольких послушников Мейнхард отбыл в Ливонию, где обратил в христианство сколько-то латышей и построил в Унхилле, что в низовьях Двины, первую церковь на этой языческой земле. Архиепископ Бремена, сознающий важность миссии Мейнхарда, рукоположил его в 1186 г. в сан епископа Ливонии. Упорная миротворческая деятельность Мейхарда не была напрасна, и христианство постепенно распространилось среди местного населения. После смерти Мейхарда в 1196 г. в возрасте семидесяти двух лет его дело продолжил монах Бертольд родом из Ганновера, который прибыл в Ливонию, когда язычники снова подняли мятеж. Бертольд был убит в июле 1198 г. во время вооруженного столкновения. Местные старейшины решили изгнать всех священников, обосновавшихся в тех краях; они поставили ультиматум, что если до Пасхи 1199 г. они не уберутся отсюда, то будут убиты. В такой ситуации в Ливонию был направлен молодой и энергичный Альберт фон Буксховден из епархии Бремена, которому помогал брат Теодорик. В 1199 г. Альберт был избран епископом Ливонии.

Новый епископ пользовался поддержкой папы Иннокентия III, Филиппа Швабского, короля Дании, немецкой и датской Церквей. Альберт Ливонский мечтал создать на землях язычников Балтийского побережья независимое государство под единой папской властью. По его просьбе папа Иннокентий III в октябре 1199 г. издал буллу, призывающую «христиан Саксонии и Вестфалии» примкнуть в крестовому походу «для защиты Ливонской Церкви за прощение грехов». Действительно, в апреле 1200 г. многочисленные «крестоносцы» отправились в Ливонию, чтобы поддержать епископа Альберта. Сочетая миссионерскую деятельность и колонизаторскую, епископ Ливонии основал в 1201 г. город Ригу, который стал опорным пунктом его епархии. Многочисленные колонисты, пришедшие с севера Германии, главным образом из Бремена и Гамбурга, обосновались в городе, население которого росло, и вскоре город стал главным торговым портом региона. Но необходимо было обеспечить надежную защиту христианских поселений, непопулярных среди населения, в подавляющем своем большинстве язычников.

Как только крестоносцы вернулись к себе, епископ Ливонии задумался над тем, чтобы создать военный орден, наподобие тех, что уже существовали в Святой земле, где убедительно доказали свою эффективность. Альберт послал в Рим брата Теодорика, дабы сообщить о своем проекте. По возвращении Теодорика осенью 1202 г. проект нашел свое воплощение в утверждении и организации военного и религиозного ордена Братьев воинства Христова (Fratres milinae Christi), устав которого был официально утвержден в 1204 г. папской буллой, которая предоставляла ордену те же права, что и ордену тамплиеров. Братья больше известны под другим названием — рыцарей-меченосцев (Schwertbruder) из-за белого плаща, аналогичного плащу госпитальеров, с мечом красного цвета на плече.

Епископ Ливонский посчитал, что одного лишь присутствия рыцарей-меченосцев достаточно, чтобы умиротворить Ливонию. Правда и то, что дважды, в 1207 г., затем в 1212 г., ливонцы и латыши, которые попытались напасть на позиции ордена, были разгромлены и вынуждены покориться, но верно и то, что языческие верования не умирали, а продолжали жить в душах местного населения.

Обосновавшись в Риге, епископ Адальберт посвятил себя строительству церквей в Ливонии; он основал несколько монастырей, среди которых Дунамунд (Daugavriva) в 1205 г., где аббатом стал Теодорик, его брат, и где в 1208 г. осели монахи-цистерцианцы. Но Альберт не отстранился от выполнения своей миссии. Его поддерживали меченосцы, он мог рассчитывать на помощь короля Германии Филиппа Швабского, из рук которого получил в лен ливонское епископство, что дало ему титул князя империи и на этом основании право жаловать в ленное владение часть земель епископства своим вассалам.

Чтобы расширить земли епископства, Альберт, правда тщетно, попытался в 1208 г. обратить эстонцев Тарту и Отепаа в христианство и рукоположил брата Теодорика в 1211 г. в епископы Эстонии. Но эта эстонская епархия оказалась иллюзией, так как эстонцы непримиримо отнеслись к попытке обратить их в христианство.

Ситуация была аналогичной и с пруссами, чьи грабительские набеги с трудом сдерживали поляки; особенно часто от них страдала Мазовия. Князь Мазовецкий призвал на помощь короля Дании Вальдемара II, чье вмешательство оказалось малоэффективным. Пруссы в ответ напали на Мазовию весной 1206 г. Князь Мазовецкий Конрад был братом короля Польши, Владислава Белого, но из-за беспорядков в собственной стране король был не в состоянии предоставить необходимую помощь. Конрад обратился к миссионерам, считая, что мирными переговорами можно добиться лучших результатов.

Одним из этих миссионеров был монах-цистерцианец Христиан из монастыря Оливы (этот монастырь Олива был основан в 1186 г. в восточном Поморье, на оконечности Гданьского залива, на границе с прусскими землями), родом из Фрейенвальда, который, помимо немецкого, прекрасно владел польским и прусским. Христиану удалось обратить в христианство нескольких прусских старейшин reiks (королей) Лобау и Ланзамы в Помезании (район Эльблонга), за что в 1214 г. был рукоположен в епископы Пруссии папой Иннокентием III, к которому он явился с докладом о выполненной миссии. Но пока он был в Италии, пруссы восстали и убили новообращенных. Они ворвались в Мазовию и разграбили кульмскую (хелминскую) землю. Князю Конраду было разрешено Римом призвать к крестовому походу, и вот мощная армия крестоносцев, состоящая главным образом из немцев, поляков и датчан, выступила против пруссов в 1219 г. Христиан, в качестве епископа Пруссии, получил от князя Мазовии обширные земли в районе Хелмно; этот дар был подтвержден папой. Пруссы сделали вид, что подчинились, но как только крестоносцы ушли с их земли, возобновили свои набеги, в 1223 г. снова вторглись в Мазовию, захватили город Плоцк, разграбили его и увели в рабство множество пленных.

Дабы обеспечить безопасность в этом регионе, Христиан предложил в 1225 г. князю Мазовии создать военный орден, вроде ордена меченосцев. Это был орден «Братьев воинства Христова в Пруссии», рыцари которого носили на белых плащах изображение креста и меча красного цвета. Рыцари получили от князя Мазовецкого Добжинский замок (откуда их прозвище «добжинские братья»). Помимо Добжинского замка, резиденции великого магистра ордена, рыцари получили обширные территории, расположенные на окраине прусских земель. Их целью было обращение пруссов в христианство и покорение их: в случае удачи половина завоеванных ими земель переходила во владение рыцарей.

Пруссы ответили на это новыми набегами на герцогство Мазовия. Добжинские рыцари попытались их остановить, но были разбиты в 1225 г. возле Страсбурга (Бродника), а те немногие, кто выжил, вернулись в замок; князь Мазовии бежал. В очередной раз те, кто попытался обосноваться в Пруссии, потерпели сокрушительное поражение.