Yaroslav, to back up an armistice signed with Constantinople in 1046, had married his fourth and favorite son by Ingigerd Olafsdottir, Vsevolod, to the Greek Anastasia (d. 1067), who tradition holds was a daughter of Emperor Constantine IX Monomachos by his second wife (he gained the Imperial throne through his third marriage), but no reliable source has ever been found to confirm this.

However, the couple's son Vladimir Monomakh bears the family name of that emperor, giving the story credence.

Upon his father's death in 1054, Vsevolod receives in appanage the towns of Pereyaslav, …