Впрочем, одного города, населенного немцами, было недостаточно. Его население не могло предаваться мирным занятиям, так как приходилось вести непрерывную борьбу с ливами. Следовательно, нужно было военное сословие, которое бы взяло на себя обязанность постоянно бороться с коренным населением. Для этого Альберт стал вызывать рыцарей из Германии и давать им замки в ленное владение. Однако рыцари ехали крайне неохотно.
Тогда Альберт решил основать орден «воинствующей братии» по образцу военных орденов в Палестине. Папа Иннокентий III одобрил эту идею, и в 1202 году был основан орден рыцарей Меча, получивший устав Храмового ордена. Рыцари ордена носили белый плащ с красным мечом и крестом, вместо которого после стали нашивать звезду. Первым магистром ордена был Винно фон Рорбах.
Первое время отношения между орденом и рижским епископом были хорошие, но через несколько лет они испортились, и тогда фон Рорбах перенес свою резиденцию из Риги в крепость Венден.
Полоцкие князья вовремя не осознали угрозу, которую им и другим русским княжествам несут немцы. Лишь в 1203 году полоцкий князь Володша с дружиной внезапно осадил Укскуль. Немцы заплатили ему большой выкуп, после чего Володша пошел осаждать крепость Гольм. Однако там немцы отразили штурм с помощью метательных машин, бросавших на осаждающих тяжелые камни и бревна. Володше пришлось увести свою дружину назад в Полоцк.
Подчинив ливов, живших вблизи балтийского побережья, крестоносцы двинулись на восток и разрушили русские города Кукейнос и Герсик, где княжили вассалы полоцкого князя Вячеслав Борисович и Всеволод Борисович, правнуки Всеслава Чародея.
В то время, когда немцы утверждались в Ливонии, отнимая низовые двинские земли у Полоцкого княжества, новгородцы и псковичи продолжали бороться с чудью (т.е. с предками нынешних эстонцев), жившей к югу от Финского залива. В 1176 году вся Чудская земля, по выражению летописца, «приходила под Псков, но была отбита с большим уроном».
В 1190 году чудские племена по озеру пришли на судах к Пскову. Псковичи славно встретили гостей: в летописи сказано, что ни один «чунец» не ушел живым. Однако другому отряду чухонцев удалось захватить город Юрьев. В следующем 1191 году псковичи и новгородцы объединились, отбили Юрьев, огнем и мечом прошлись по Чудской земле, «полону приведе без числа». В 1192 году псковичи опять ходили на чудь и взяли у них городище Медвежью Голову (Оденпе, с 1917 года – город Отепя). После этого чухонцы образумились, стали исправно платить дань, и до 1212 года конфликтов с русскими у них не было.
В 1212 году чудь что-то натворила, и новгородский князь Мстислав Удалой с братом Владимиром совершили несколько походов на чудь, взяли город Медвежью Голову, дошли до побережья Балтийского моря.
На следующий 1213 год немцы захватили город Медвежью Голову, то есть вторглись в земли, которые новгородцы считали своими. В 1214 году два войска новгородцев двинулись отбивать свою вотчину. Князь Мстислав Удалой пошел в Эстляндию, а Всеволод Борисович, тот самый, у которого немцы отняли Герсик, пошел на Ливонию. Крестоносцы со всей Ливонии заперлись в Риге. Всеволод по неясным причинам брать Ригу не стал, а вернулся в Новгород.
Надо сказать, что епископ Альберт и крестоносцы действовали не только кнутом, но и пряником. В 1210 году Альберт заключил с полоцким князем Володшей мир и обязался платить ему дань за ливонские земли. Через несколько лет немцы перестали платить Полоцку дань, а тамошний князь удовольствовался помощью немцев против Литвы и свободой плавания по Западной Двине. Крестоносцам удалось сделать своим «агентом влияния» полоцкого князя Владимира Мстиславовича. Князь даже выдал свою дочь за брата епископа Альберта.