Судя по всему, именно со стремлением Всеволода Ярославича противодействовать вмешательству Польского князя Владислава I Германа (1079–1102 гг.), двоюродного брата Ярополка, связан заключённый в это время брак дочери Всеволода Ярославича Евпраксии с маркграфом саксонской Северной марки Генрихом Штаденом (1082–1087 гг.). В 1086/1087 г. Ярополк вернулся на Русь и заключил мир с Всеволодом Ярославичем. Условия договора исследователям неизвестны, но они не исключают, что Всеволоду Ярославичу пришлось отдать судьбу Ростиславичей в руки Ярополка, т.к. тот погиб в ноябре во время похода на Звенигород, стольный город Володаря. Описав данные события, летописец отмечал: «Седящу бо ему (Всеволоду Ярославичу) Кыеве, печаль бысть ему от сыновец своих, яко начаша ему стужати, хотя власти ов сея, ов же другие; сеи же, омиряя их, раздаваше власти им». После 1086/1087 г. прямые сведения в «Повести временных лет…» о неурядицах правителя Киева с подручными князьями прекращаются, что свидетельствует об известной стабилизации внутреннего положения на Руси в последние годы правления Всеволода Ярославича. В это же время происходит и укрепление внешнеполитических позиций Киева: в 1088/1089 г. овдовевшая Евпраксия была выдана отцом за германского императора Генриха IV (1056–1106 гг.), что побудило как Польшу, так и Венгрию в лице короля Ласло I Святого (на дочери которого был женат сын Святополка Изяславича Ярослав) отказаться от поддержки единственного оставшегося в живых из сыновей Изяслава Ярославича. Это позволило Всеволоду Ярославичу, судя по косвенным данным, в 1091 г. разорвать договор со Святополком о наследовании тем киевского стола, в результате чего Святополк был лишён Новгородского княжения и был вынужден ограничиться Туровом. К этому времени (относя, впрочем, утрату Святополком Новгорода традиционно к 1088 г.) Валентин Лавретьевич Янин приурочивает появление характерного типа печати Всеволода Ярославича с надписью «Господи, помози рабу Своему Андрею, князю всея Руси»; в таком случае период 1078–1091 гг. (по В.Л. Янину, 1078–1088 гг.) следовало бы рассматривать как время официального соправления Всеволода Ярославича с племянником Святополком Изяславичем, что по династическим понятиям той эпохи выглядит маловероятным. Как полагают исследователи, возникновение формулы «князь всея Руси», уникальной для древнерусской княжеской титулатуры домонгольского периода, естественнее было бы связать с прекращением такого специфического политического строя, как соправление Ярославичей, и установлением единовластия Всеволода Ярославича в 1078 г. (как предполагал ещё первый публикатор этой печати Александр Васильевич Соловьёв), когда, по словам летописца, Всеволод Ярославич «преим власть Русьскую вьсю». Однако, по мнению исследователей, такая трактовка вступает в противоречие с уникальностью этого типа буллы Всеволода Ярославича. На заключительный период правления Всеволода Ярославича приходятся заметные нестроения в государственном управлении, причину которых летописец видит в неоправданном предпочтении князем младшей дружины перед старшей: «Нача любити смысл уных, съвет творя с ними… и нача… людем не доходити княже правды, и начаша тиуны его грабити люди и продаяти (налагать судебные штрафы), сему не ведущу в болезнех своих».