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