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