Чехарда князей в Галиче на этом не закончилась, и в 1219 г. великий князь Польши Лешко Белый, вопреки прежним договоренностям с королем Венгрии, пригласил на галицкое княжение князя Мстислава Мстиславича Удатного (или Удалого), княжившего в то время в Великом Новгороде. Князь Мстислав без особой борьбы занял Галич, а для упрочения своих позиций в этом регионе выдал замуж свою дочь за князя Даниила Романовича. Князь Мстислав предполагал, что основным его противником будет венгерский король, но ошибся: стал прежний друг Лешко непримиримым врагом, не пожелавший возвращать Даниилу захваченные у него ранее волынские города. Лешко Белый вновь пообещал королю Андрею отказаться от своей части Галиции в пользу зятя – королевича Коломана после победы над Мстиславом Удатным и Даниилом. Объединенные польско-венгерские войска одержали временную победу над галицким и волынским князьями, но уже в 1220 г. Мстислав вернулся, приведя с собой значительное войско половцев. С их помощью он разгромил войска Андрея II и Лешко Белого, при этом большое количество побежденных поляков и венгров было уведено в рабство половцами. В плен к князю Мстиславу попал даже королевич Коломан со своей польской женой.
Коломана князь Мстислав Удатный, конечно, отпустил к отцу, но на условиях отказа его от Галича, а также согласия короля Андрея на брак своего младшего сына, тоже Андрея, и Марии, третьей дочери князя Мстислава. По брачному договору Галич через три года должен был бы перейти в наследство Марии, а город Перемышль вместе с населением передавался ей в качестве приданого. При этих условиях дочь Лешка теряла права на Галич, и венгерско-польский союз развалился. С другой стороны, Даниил тоже лишался Галича, из-за которого вроде бы все эти распри и начинались.
Затем в 1223 г. произошла битва русских князей под руководством Мстислава Мстиславича, Мстислава Святославича и Мстислава Романовича с татаро-монгольским войском на Калке. Битву русские князья проиграли, в живых из трех Мстиславов остался один Мстислав Удатный, который вернулся в Галич вместе с раненным в этой битве Даниилом. Странно, но жизнь в русских княжествах после разгрома их войск на Калке шла и дальше своим чередом, как будто ничего не случилось. Князья продолжали ссориться между собой, в том числе и Мстислав, который, поверив клевете, начал усобицу против Даниила, а тот призвал себе на помощь Лешко Белого. Даниил отвоевал у Мстислава города Белз и Червен, а поляки – часть Галиции. Мстислав грозился снова привести половцев, но тут вдруг открылась ему правда о клеветниках на Даниила, и эти два князя вновь стали союзниками. Король Андрей и великий князь Лешко тоже в очередной раз объединились и начали новую войну против Мстислава и Даниила, заняв многие пригороды Галича. Войну Мстислав и Даниил выиграли, венгерские и польские войска покинули Галицию и Волынь, но затем в результате интриг галицких бояр Мстислав опять передал Галич королевичу Андрею, после чего вскоре умер в 1228 г., пережив на год Лешко Белого.
Волынский князь Даниил вместе с братом Васильком в качестве союзников Конрада Мазовецкого отправились в 1229 г. в поход в Польшу против Владислава Ласконогого. Захватив по пути несколько польских городов, русские войска дошли до Силезии, где под городом Калишем был заключен русско-польский мирный договор.
Конрад I Мазовецкий (1187–1247), ставший с помощью русских войск великим князем Польши, в свое правление столкнулся с еще одной проблемой – агрессией пруссов. Когда в 1138 г. Польша распалась на отдельные княжества, Западное и Восточное Поморье стали самостоятельными землями, в которых возникли свои династии, никак не связанные с династией Пястов. Но уже в 1181 г. князь Западного Поморья Богислав I стал ленником императора Фридриха Барбароссы, а затем его земли вошли в состав империи. Отделению от Польши способствовало и то, что епископство Волин не подчинялось архиепископу Гнезно, а оставалось независимым. Восточное Поморье, став сначала независимым во главе с князем Самбором, затем опять признало власть князей Великой Польши, но все-таки в 1227 г. стало независимым герцогством. Однако внутренние усобицы не позволили реализовать эту независимость для усиления централизованной власти. Еще в 1226 г. разгорелась борьба за власть между братьями – Самбором II и Ратибором и сыновьями – Мествином II и Варциславом II. В борьбе против Варцислава Мествин сначала заручился поддержкой маркграфа Бранденбургского, а впоследствии стал его ленником. Таким образом, почти все Поморье попало в зависимость от германских властителей.
К тому времени в течение уже двух столетий германские миссионеры делали попытки христианизации пруссов – то относительно успешные, то наоборот: миссионеров убивали, а крещеные пруссы возвращались в язычество. В начале XIII в. христианизацией пруссов занялись монахи ордена цистерцианцев, которые для начала организовали монастырь в Лекно, неподалеку от Познани и Гнезно. В 1206 г. аббат этого монастыря Готфрид посетил в Риме папу Иннокентия III, который специальной буллой поручил аббату миссию христианизации среди пруссов. Однако что-то не заладилось с этой миссией у цистерцианцев, и аббат Готфрид сложил с себя обязанности духовного пастыря своих братьев-монахов, под именем Христиана продолжив христианизацию пруссов в одиночку. Он достиг личной проповедью значительных успехов в крещении пруссов, но сами пруссы, попадая под влияние пастырей поморских и польских земель, практически становились рабами влиятельных князей, несмотря на заступничество за них самого Христиана. Пруссы в ответ поднимали восстания и отрекались от христианства, становясь вероотступниками.
В 1216 г. польское духовенство и князья, а также ставший прусским епископом Христиан обратились к римскому папе за разрешением участвовать в крестовом походе в Пруссии тем, кто принял обет следовать в Палестину для освобождения Иерусалима. Папа Гонорий III пошел им навстречу и даровал участникам прусских крестовых походов то же отпущение грехов, что и идущим в Палестину. В 1218 и 1221–1223 гг. войска крестоносцев сражались «за спасение душ» пруссов, пытаясь вернуть отступников на путь истины, а заодно «уговорить» пруссов-язычников принять крещение. Крестоносцы были выходцами из соседних германских и польских земель, в том числе земель силезского князя Генриха Бородатого, оспаривавшего первенство у князя Конрада Мазовецкого.
Среди крестоносцев князя Силезии были также члены духовно-рыцарских орденов тамплиеров и тевтонцев. Тамплиеры в то время создавали свой филиал в Великой Польше как бы для защиты ее границ. Но не имея единого командования, движение крестоносцев в Пруссии не достигло желаемого для христиан результата. Разрозненные действия отдельных отрядов только привели к сплочению прусских племен, понимавших, что дело не столько в обращении в христианство, сколько в их порабощении. А вопрос превращения пленных пруссов в рабов стоял настолько остро, что даже папа Гонорий III вынужден был обратиться к крестоносцам с увещеваниями и запретил им вторгаться в Пруссию без позволения епископа Христиана, а пленных язычников обязал передавать ему для крещения.
После отступления крестоносцев, потерявших интерес к военным действиям в Пруссии, сами пруссы перешли в наступление и заняли значительную часть Мазовии. Не имея возможности самостоятельно противостоять прусской агрессии, Конрад Мазовецкий обратился за помощью к верховному магистру Тевтонского ордена Герману фон Зальца. Однако стороны в течение нескольких лет не могли договориться: тевтонцы хотели навсегда обосноваться в землях, которые они завоюют, а поляки рассчитывали, что эти земли тевтонцы передадут Польше на определенных условиях.
Чтобы получить правовое оправдание вторжения в Пруссию, орден добился издания императором Фридрихом II в 1226 г. соответствующей грамоты, которая вошла в историю под названием Золотая булла из Римини. В грамоте говорилось о сообщении императору верховным магистром Тевтонского ордена Германом фон Зальца просьбы Конрада Мазовецкого помочь ему в борьбе против пруссов, а также о его намерении пожаловать ордену Кульмскую землю и земли близ Пруссии, чтобы орден мог выступить против пруссов, а также о том, что верховный магистр просит императора признать и утвердить обещанное Конрадом. За этим в булле следовало соответствующее решение императора об утверждении за орденом этих земель со всеми правами и освобождением их от повинностей. Столь категоричное решение основывалось на том, что Фридрих считал все эти земли, отвоеванные в конце VIII в. у Аварского каганата Карлом Великим, собственностью Германской империи.