Вскоре русское войско, в которое вошли дружины всех видных русских князей (не пришел лишь, сославшись на болезнь, черниговский князь Олег, старинный друг половцев), а также пешие полки, выступило в весеннюю степь. Решающая битва с половцами произошла 4 апреля близ урочища Сутень, неподалеку от Азовского побережья. На стороне половцев в ней принимали участие более 20 видных ханов. Летописец позднее записал: «И поидоша полкове, аки борове, и не бе презрети ихъ. И Русь поидоша противу имъ» («И двинулись полки половецкие, как лес, конца им не было видно; и Русь пошла им навстречу»). Но на истомленных долгой зимой конях половцы не сумели нанести своего знаменитого стремительного удара. Их войско было рассеяно, большинство ханов убиты. Хана Бельдюза взяли в плен. Когда он предложил за себя огромный выкуп, Мономах сказал ему, что хан предлагает просто вернуть награбленное на Руси, и приказал зарубить его в назидание другим. А затем русские дружины пошли по половецким «вежам», освобождая пленников, захватывая богатую добычу, отгоняя к себе табуны коней, стада.

Это была первая большая победа русов в глубине степи. Но до основных становищ половцев они так и не дошли. На три года прекратились половецкие набеги. Лишь в 1105 г. половцы потревожили русские земли. Они воспользовались тем, что русские князья были втянуты в этот год в войну с полоцким князем. На следующий год половцы нагрянули снова. Через год объединенное войско Боняка и Шарукана опять появилось на Руси, разоряя киевские и переяславские земли. Объединенное войско русских князей неожиданным встречным ударом опрокинуло их на реке Хорол. Русы зарубили брата Боняка, едва не пленили Шарукана, захватили огромный половецкий обоз. Но основные силы половцев ушли восвояси.

И снова затихли половцы. Но теперь русские князья не стали ждать новых набегов. Дважды русские дружины наносили удары по половецкой территории. С ближними же, дружественными, половцами закреплялись мирные отношения. В эти годы Мономах и Олег женили своих сыновей, Юрия Владимировича (будущего Юрия Долгорукого) и Святослава Ольговича, на дочерях союзных половецких ханов. Так в семье Рюриковичей кроме славян, шведов, греков, англичан появилась и половецкая династическая линия.

В 1111 г. Русь организовала против половцев грандиозный поход, который достиг сердца их земель – города Шарукань вблизи Дона.

Этот поход начался необычно. Когда в конце февраля войско подготовилось к выходу из Переяславля, то впереди него выступили епископ, священники, которые с пением вынесли большой крест. Его водрузили неподалеку от ворот города, и все воины, в том числе и князья, проезжая и проходя мимо креста, получали благословение епископа. А затем на расстоянии 11 верст представители духовенства двигались впереди русского воинства. В дальнейшем они шли в обозе войска, где находилась и вся церковная утварь, вдохновляя русских воинов на ратные подвиги.

Мономах, бывший инициатором этой войны, придал ей характер крестового похода – по образцу Крестовых походов западных властелинов против мусульман Востока. Инициатором тех походов выступил папа Римский Урбан II. А в 1096 г. начался Первый крестовый поход западных рыцарей, закончившийся взятием Иерусалима и созданием рыцарского Иерусалимского королевства. Священная идея освобождения «Гроба Господня» в Иерусалиме от рук неверных стала идеологической основой этого и последующих походов западных рыцарей на Восток.

Сведения о Крестовом походе и освобождении Иерусалима быстро распространились во всем христианском мире. Было известно, что во Втором крестовом походе принимал участие граф Гуго Вермандуа, брат французского короля Филиппа I, сын Анны Ярославны, двоюродный брат Мономаха, Святополка и Олега. Одним из тех, кто принес эти сведения на Русь, был игумен Даниил, побывавший в начале XII в. в Иерусалиме, а потом оставивший описание своего путешествия о пребывании в крестоносном королевстве. Даниил был в дальнейшем одним из сподвижников Мономаха. Возможно, ему и принадлежала идея придания походу Руси против «поганых» характера крестового похода. Этим и объясняется та роль, которую отвели духовенству в этом походе.