На пути Ярослав попросил повернуть в сторону двора сына Всеволода. Он хотел проститься со своим последним родившимся внуком — первенцем Всеволода — Владимиром, в христианстве Василием. Этот внук был особенно дорог Ярославу, потому что родился он во искупление тех несчастий, что понесла Русь в недавней войне с Византией. В 1042 году на престол в империи встал Константин IX Мономах, который сразу же отодвинул от трона всех, кто ранее поддерживал его противников, — Михаила IV и Михаила V, и одними из первых пострадали русские купцы, русский монастырь на Афоне. Пристань и купеческие склады были разграблены сторонниками Константина Мономаха, убийство русского посла переполнило чашу терпения Ярослава, и в 1043 году он послал на Константинополь по примеру Олега, Игоря и Святослава свою рать. В поход по воде двинулось двадцать тысяч человек во главе со старшим Ярославовым сыном, князем новгородским Владимиром и боярином Вышатой Остромиричем. Князь вел в поход дружину; Вышата — прочих воев: вооруженных смердов, ремесленников. Константин было опомнился, попытался покончить дело миром, послав навстречу руссам на Дунай послов с подарками и мирными предложениями, но руссы продолжали свое движение. Однако Владимиру не суждено было повторить подвиги Олега. Его ждала судьба Игоря. Буря разметала и потопила многие русские корабли, и даже сам князь был вынужден пересесть в другую ладью. Но попытка греков разгромить княжескую дружину на море окончилась неудачей: Владимир разбил посланный против него византийский отряд и вернулся в Киев. Труднее пришлось воям Вышаты: выброшенные на берег, они решили добираться на родину посуху, но на обратном пути около Варны их настигло войско Кекавмена, руссы были разгромлены и пленены. Шесть тысяч пленников Константин приказал жестоко наказать. Одним из них выкололи глаза, другим отрубили правую руку, чтобы никогда не поднимали они меч против великой империи. Ярослав готовил новый поход против греков, заслал посольства к своим друзьям в окрестные страны, прося помощи, но в это время в Киев пришли послы из Константинополя. Император обещал возместить весь ущерб, нанесенный русским купцам и монастырю, отпустить на родину пленных, отдать в жены еще неженатому Ярославову сыну, шестнадцатилетнему Всеволоду, свою внебрачную дочь Анастасию, рожденную от любовницы Склирины. В 1046 году был заключен мир, а вскоре в Киеве появились первые отпущенные греками русские пленники. В рубищах, седые, с темными впадинами вместо глаз, с завернутыми за пояс пустыми правыми рукавами рубах брели они от пристани в устье Почайны, вдоль Подола и далее на гору, вызывая ужас и сожаление у киевлян, а потом иные из них появились в Новгороде и Чернигове, Переяславле и Смоленске, в селах и погостах. Печаль опустилась тогда на Русскую землю. И когда, прибыв с большой свитой, императорская дочь сошла на берег, держа в руках данную ей отцом икону богородицы, ее встретили напряженным и печальным молчанием. Венчание происходило в огромной Десятинной церкви, воздвигнутой еще при Владимире сразу же после крещения Руси, а потом Всеволод с молодой женой отбыл на княжение в Переяславль.
Родился же первенец Всеволодов в 1053 году в Киеве, потому что переяславский князь, ходивший у отца в любимцах, мало жил в своем стольном городе и больше времени проводил возле отца в великокняжеском киевском дворце. Здесь же, во Всеволодовых хоромах, и появился на свет будущий великий князь киевский Владимир II Мономах.
По старославянскому обычаю ему дали два имени, и оба в честь великого князя Владимира I. Имя выбирал сам дед, великий князь Ярослав, Всеволод же, как всегда, согласился с отцом, и уже на склоне лет Владимир Всеволодович написал в своем «Поучении»: «Я худой, дедом своим благословленным, славным нареченный во крещении Василий, русским именем Володимир». Но вопреки установившемуся обычаю мать и отец решили, кроме того, наречь его и еще одним именем, в честь византийского деда Константина IX — Мономахом. Тогда задумался великий князь: слишком много бед и печалей было связано у Руси с этим именем, но потом сказал: «Пусть будет так» — время пройдет, уйдут в прошлое вместе с людьми сегодняшние обиды и печали. А имя византийского императора так и останется за его внуком, наследником Всеволода, и, может быть, поможет ему в нелегкой борьбе за власть со своими недругами, с властелинами окрестных стран.
Ярослав Владимирович, ведомый под руки, вошел в хоромы, не снимая шубы, прошел в детскую, кормилица отодвинулась в сторону, и он склонился над колыбелью. Оттуда прямо на него смотрели два совершенно прозрачных светло-голубых глаза, золотая прядка волос падала на лоб младенца. Ярослав скупо улыбнулся замерзшими, неживыми губами и повернулся прочь. В ту пору Владимиру Мономаху не исполнилось и года.