Единым фронтом Ярославичи выступили и против полоцкого князя Всеслава, который в 1065 г. попытался захватить Псков, а затем и Новгород. Ярославичи с огромным по тем временам войском двинулись против него. Зимой 1067 г. объединенное войско подошло к Минску. Минчане закрыли все городские ворота, приготовились к обороне, однако не выдержали натиска наступающих, которые взяли город, «перебили всех мужей, а жен и детей захватили в плен». Но еще оставалась дружина Всеслава. В начале марта противники встретились на реке Неман. «И был снег велик, – пишет летописец, – и пошли друг на друга. И была сеча жестокая, и многие пали в ней, и одолели Изяслав, Святослав и Всеволод, Всеслав же бежал». Ярославичи обещали сохранить ему жизнь и, поцеловав крест, заявили: «Приди к нам, не сотворим тебе зла». Всеслав поверил им и явился на переговоры. Но Ярославичи обманули его. Они схватили Всеслава и его сыновей, привезли в Киев и посадили в «поруб» – подземную тюрьму. Так произошло одно из первых клятвопреступлений в семействе Рюриковичей.
В это же время происходили и самостоятельные походы Ярославичей на земли своих соседей. Летопись сообщает, что в конце 1050-х – начале 1060-х годов «ходил Изяслав на прибалтийские племена и дань взял большую».
Однако в 60-е годы XI в. междоусобная борьба и столкновения с отдельными небольшими народами не представляли еще серьезной угрозы для русских земель. Гроза собирались на юге и юго-востоке, где формировались союзы половецких племен.
Половецкие орды расположились между Дунаем и Днепром, в причерноморских степях, они кочевали в пределах рек Донец и Тор, по берегам Дона. От пастбища к пастбищу передвигались половцы, все сокрушая на своем пути. Зимой они уходили к югу, поближе к теплым черноморским берегам, а летом перемещались на север. Их стада тучнели в ковыльных степях, и половцы подходили к самой кромке южнорусских земель. Осенью же, когда кони были сыты, начиналась пора набегов. В поход поднималось все взрослое население. Их конные лавины внезапно возникали перед изумленным и испуганным врагом. Вооруженные луками и стрелами, саблями, арканами и копьями, половецкие воины с пронзительным криком бросались в бой, стреляя на скаку из луков и засыпая врага тучей стрел. Сокрушив противника, они мгновенно исчезали. На месте набега оставались лишь развалины и пожарища, а за кочевниками тянулись следы многочисленных пленников, которых гнали на невольничьи рынки юга.
Тактика кочевников состояла в том, чтобы напасть врасплох, смять слабого противника, подавить его или разъединить вражеские силы, заманить их в засаду, уничтожить. Но если половцы сталкивались с сильным противником и вынуждены были отступать, они умели обороняться: быстро составляли свои телеги в несколько кругов, накрывали их бычьими шкурами, чтобы враг не мог поджечь лагерь, и, укрывшись внутри, отчаянно отбивались от неприятеля. Через проходы между телегами они совершали конные вылазки, наводя на осаждавших ужас.
Со временем, уже прочно осев в южных степях, некоторые половецкие орды стали вести полуоседлый образ жизни. У них появились постоянные становища и даже возникли небольшие городки, огороженные земляными валами. Столицей донских половцев позднее стал город Шарукань, который был назван в честь всесильного половецкого хана Шарукана.
В течение долгих десятилетий половцы вели постоянные войны с Русью, но были и длительные периоды мирных отношений. В мирное время народы вели торговлю, широко общались в приграничных районах. Русские князья и половецкие ханы нередко заключали династические браки между своими детьми. Так известно, что второй женой Всеволода Ярославича, мачехой Владимира Мономаха, была половецкая княжна.
Однако, несмотря на периоды мирного сосуществования, постоянное присутствие половцев вблизи русских границ создавало на Руси внутреннее напряжение, особенно в южных районах страны. К тому же князья в запале борьбы друг с другом нередко обращались за помощью к половцам. И русские земли начиная с последних десятилетий XI ст. периодически стали превращаться в поля кровавых междоусобных битв.
Как мы отмечали выше, первая встреча Всеволода Ярославича с половцами в 1061 г. закончилась для него плачевно. Но в 1064 г., когда половцы во главе с Сокалом вновь пришли на Русскую землю, результат оказался иным. На этот раз против них вышел Изяслав. В битве недалеко от Сновска русские дружины «12 000 половцев побили» и взяли в плен, в том числе Сокала и других князей.