В 1076 г. Владимир с двоюродным братом Олегом Святославичем (тем самым, что в будущем откажется от Ростово-Суздальской земли) уже воюет за Польшу против чехов. Здесь впервые открылся талант Мономаха как военачальника. Поход длился 4 месяца. Русские дружины бились в Силезии, прошли через Глогову (Глогау), добрались до Бемервальда (Чешского леса). После заключения мира между Польшей и Чехией Владимир и Олег оказались в трудном положении. Польский король решил не расплачиваться с русскими за их помощь. Этим вероломством он ничего не выиграл. Молодые князья не позволили себя оскорблять. Как истинные сыновья своего века они начали «пустошить» владения строптивого союзника, осадили город Глогов и не уходили из Польши, пока король не прислал им 1000 гривен серебра (около 100 кг) и прочие дары. С этой данью и другой военной добычей братья вернулись на Русь.
По возвращении домой Мономаха ждала большая радость. Он был женат на Гите, дочери последнего англосаксонского короля Гарольда. В 1076 г. родился старший сын Владимира Мономаха и Гиты — Мстислав, впоследствии ставший, как и его отец, видным государственным деятелем и полководцем и прозванный еще при жизни Мстиславом Великим. В крестные отцы для новорожденного Мстислава Владимир позвал друга по польскому походу Олега Святославича.
Еще не закончились пиры в честь рождения Мстислава, а его отец уже скакал в Смоленск, где будоражили народ языческие волхвы. В 1077 г. Владимир воевал с Полоцком.
На поле брани Владимир Мономах одерживал одну победу за другой. С 13 до 25 лет он совершил 20 военных походов («великих путей», по выражению самого Владимира Мономаха; всего на его жизнь придется 83 «великих пути»). Историки посчитали, что, исходя из тех мест, куда направлялись походы Мономаха, он за первые 12 лет своей самостоятельной княжеской карьеры должен был преодолеть в седле не менее 10000 км.
Необычайно везло Владимиру Мономаху и на политическом поприще. С 13 лет он княжил в обширной Ростово-Суздальской земле, а в 20 (в 1073-м) сел на третий по старшинству русский стол в Переяславле-Русском в обход своих двоюродных братьев (более старших по родовому счету). Расчетливый Всеволод, переместившись в освобожденный Святославом Чернигов, заранее оговорил, что и Переяславль останется в его семье и отойдет Владимиру. Конечно, Всеволоду было жаль отдавать Переяславль, как того требовал предложенный Ярославом Мудрым порядок, племянникам. Всеволод 19 лет (с 1054 по 1073 г.) княжил в Переяславле, укрепил и украсил этот город.
Очень бурными, но очень удачно завершившимися для Владимира Мономаха оказались 1076 — 1078 гг. В 1076-м умер великий князь киевский Святослав. На его место было въехал отец Мономаха Всеволод, но Изяслав на этот раз решил постоять за свои права. Во главе польского войска он двинулся на Русь. Дружины Всеволода возглавил Владимир Мономах. Ученый князь Всеволод был плохим воеводой, его военные успехи начались лишь тогда, когда возмужал его сын и стал вместо отца водить полки. Но если военачальником Всеволод был плохим, то политиком тонким и изворотливым. До битвы русских дружинников с польскими рыцарями в 1076-м не дошло. Противники оценили силы друг друга и договорились. Всеволод уступал Киев Изяславу. Очевидно, он представил Изяславу переворот 1073 г. как исключительную инициативу Святослава. Изяслав в благодарность за возвращенный Киев разрешил Всеволоду оставить за собой и Чернигов, где должен был сидеть сам Всеволод, и Переяславль с Ростово-Суздальской землей и Новгородом Великим, где находились дети и внук Всеволода. Таким образом, Всеволод окончательно превращался в самого могучего реального правителя Руси.