Венгерский король Андрей, услышавши о несчастье, постигшем сына, отправил к Мстиславу требование отпустить пленника, в противном случае грозил послать огромное войско. Но Мстислава нельзя было испугать угрозами. Он отвечал, что победа зависит от Бога и он, Мстислав, надеясь на Бога, готов встретить неприятельские силы. Король мало-помалу оставил свой горделивый тон: супруга его особым посольством умоляла Мстислава сжалиться и отпустить сына. Со своей стороны, бояре, вскоре заметившие слабые стороны характера Мстислава, приобрели на него влияние и всячески располагали к миру с венгерским королем. Мстислав, при всей своей храбрости и воинственности, всегда был расположен к миру и прибегал к войне только тогда, когда противники не хотели мириться на условиях, которые он признавал согласными с правдой. В 1221 году Мстислав не только помирился с венграми и поляками, но заключил дружественный договор с венгерским королем, обручил дочь свою Марию с его сыном Андреем и отдал будущему зятю во владение Перемышль.
Но через два года судьба призывала Мстислава к иному подвигу. В то время как русские князья и дружины их тратили силы в междоусобиях, в неведомых восточных странах совершались великие перевороты. На северной границе китайской империи хан Темучин, властитель монголов, народа, прежде подвластного татарам-ниучам, сделался сам повелителем многочисленных татарских племен, разорил часть китайской империи и взял Пекин, потом обратился на запад, завоевал и разорил могущественную и цветущую империю турков харазских 1 и положил основание обширнейшей империи, когда-либо существовавшей в Азии. Он владел неизмеримыми пространствами от Амура до Волги, повелевал множеством народов, составлявших его военную силу, и был прозван Чингис-Ханом, т. е. великим ханом. Его завоевательные движения достигли до половцев. Татары столкнулись с половцами на восточном берегу Каспийского моря, где половцы были заодно с аланами (жителями Дагестана). Чтобы отвлечь половцев от этого союза, предводители полчища, посланного Чингис-Ханом, сначала коварно сдружились с ними, уверивши их, что татары, будучи одного с ними племени, не хотят действовать против них враждебно.
Половцы доверились им и отстали от аланов; но потом монголы, разделавшись с аланами, покорили и половцев. Половецкие князья, уже крещеные, Юрий Кончакович и Данило Кобякович были убиты. Татары гнались за их товарищами до вала Половецкого, отделявшего землю половецкую от русской.
Половецкий хан Котян, тесть Мстислава Удалого, прибежал в Галич к зятю со страшным известием, что идет с востока несметная сила неведомых завоевателей.