Владимир был первенцем переяславского князя Всеволода Ярославича, четвёртого сына великого киевского князя Ярослава Мудрого. При крещении он получил ещё одно имя — Василий. (В течение нескольких веков русские князья носили, как правило, по два имени: одно княжеское, употреблявшееся в обычной жизни, а другое крестильное, используемое преимущественно в церкви.) По словам самого Мономаха, оба имени были даны ему дедом, князем Ярославом Мудрым, — очевидно, в память о прадеде, князе Владимире Святом, Крестителе Руси, звавшемся в крещении Василием. Возможно, престарелый Ярослав даже приезжал в Переяславль, чтобы лично присутствовать при крещении внука и поздравить невестку, мать Владимира, хотя более вероятно, что Владимир появился на свет в Киеве, где подолгу жил его отец. Во всяком случае, впоследствии, на склоне лет, князь Владимир Всеволодович начнёт своё знаменитое «Поучение» с таких исполненных гордости слов:
Яз, худый, дедом своим Ярославом, благословленным, славным, нареченный в крещении Василием, русским именем Владимир, отцом возлюбленным и матерью своею — Мономахи...
Его появление на свет стало событием, выходящим за рамки одной только русской истории. Отец Владимира, переяславский князь Всеволод Ярославич, получил в жёны не просто одну из иностранных принцесс, но византийскую царевну, дочь правящего в Византии императора Константина IX Мономаха (1042—1055). Родовое имя последнего — а в переводе с греческого оно значит: «Единоборец» — перешло к русскому князю. Так Владимир оказался внуком сразу двух могущественных правителей — Руси и Византии. Позднее киевский митрополит грек Никифор напишет, обращаясь к Владимиру — тогда уже киевскому князю — и имея в виду его необычное происхождение:
Его же Бог... из утробы освятил и помазал, от царской и княжеской крови смесив...
Брак Всеволода Ярославича положил конец русско-византийской войне 1043 года. Когда он был заключён, в точности неизвестно (во всяком случае, не ранее 1046 года), как неизвестно и имя супруги русского князя. Чаще всего полагают, что мать Мономаха звали Марией; об этом свидетельствует известная в двух экземплярах печать с греческой надписью:
Константин Мономах, представитель одного из самых знатных семейств Византии, стал императором в 1042 году, вступив в брак (третий для него) с 64-летней императрицей Зоей, дочерью императора Константина VIII. По вполне понятным причинам этот брак остался бездетным, и со смертью Константина IX (8 января 1055 года) царская династия Мономахов пресеклась, так, по существу, и не успев начаться. Русский князь Владимир Всеволодович, между прочим, оказался единственным прямым потомком Константина Мономаха (пусть и по женской линии). Впоследствии, в годы смут и постоянных перемен на византийском престоле, в Константинополе не могли не помнить об этом. Правда, сам Владимир, как можно догадываться, вовсе не спешил реализовывать свои гипотетические права на византийский престол.