Не имея опасных совместников внутри России; Всеволод старался утвердить безопасность границ своих. Половцы за деньги служили ему, но в то же время, кочуя от нынешней Слободской Украинской до Саратовской Губернии, беспокоили его южные владения, особенно же пределы Рязанские: он сильным ополчением устрашил варваров, ходил с юным сыном, Константином, во глубину степей, везде жег зимовья Половецкие, и Ханы, сняв свои многочисленные вежи, от берегов Дона с ужасом бежали к морю.

[1196—1201 гг.] Чего Андрей желал напрасно, то сделал хитрый Всеволод: он на несколько лет совершенно подчинил себе мятежную первобытную столицу наших Князей. Во время раздора его с Ольговичами, повинуясь ему, лучшие Новогородцы, не только военные люди, но и самые купцы, ходили с Ярославом в Великие Луки, чтобы удерживать Кривских Владетелей и препятствовать их соединению с Черниговцами. Ярослав Владимирович уже имел тогда многих неприятелей в Новегороде: Посадник, чиновники ездили ко Всеволоду, прося его, чтобы он вывел от них свояка и дал им сына. Великий Князь задержал сих Послов, а Новогородцы, тем оскорбленные, изгнали Ярослава, к сожалению добрых, миролюбивых людей, которых сторона редко бывает сильнейшею. Народ, обольщенный безрассудными, хотел доказать свою независимость, и сын Князя Черниговского, избранный большинством голосов, приехал в Новгород, не господствовать, но быть игралищем своевольных. Между тем Ярослав, с согласия жителей, остался в Торжке; брал дань в окрестностях Мсты и за Волоком. Новогородцев везде ловили как неприятелей, толпами приводили в Владимир. Действуя осторожнее Андрея, Всеволод не думал осаждать их столицы: мешал им только купечествовать в России и собирать налоги в Двинской земле, зная, что любостяжание скоро одержит верх над упрямством людей торговых. В самом деле, чрез шесть месяцев сын Князя Черниговского должен был ехать назад к отцу: Сотники Новогородские явились во дворце у Всеволода, извинялись, молили, обещали, и Ярослав к ним возвратился, провождаемый множеством их освобожденных сограждан. Народ торжествовал прибытие сего Князя как отца и благотворителя, удивляясь своему прежнему заблуждению. Тишина восстановилась: Князь властвовал благоразумно, судил справедливо, взял нужные меры для защиты границ и смирил Половчан, дерзнувших вместе с Литвою злодействовать вокруг Великих Лук. Но Всеволод, недовольный свояком, призвал его к себе, и чего прежде не хотел сделать в угодность народу, то народ сделал в угодность Великому Князю: Архиепископ Мартирий и чиновники должны были, исполняя уже не свою волю, а повеление Государя, ехать в Владимир и требовать Всеволодова сына на престол Новогородский. Послы сказали: «Господин Князь Великий! Область наша есть твоя отчина : молим, да повелевает нами родной внук Долгорукого, правнук Мономахов!» Всеволод изъявил притворную нерешимость; хотел еще советоваться с дружиною и как бы из снисхождения дал Новогородцам сына, именем Святослава-Гавриила, еще младенца, предписав им условия, согласные с честию Княжескою. Сей Государь, обласкав, угостив чиновников, без сомнения не мог уверить их, что славная воля Новогородская остается в древней силе своей; однако ж хотя наружным образом почтив устав ее, скрыл действие самовластия от простых граждан. Они думали, что Святослав ими избран, и встретили его с радостию. Другие видели повелителя, но молчали, ибо надеялись жить спокойнее или боялись сильного Всеволода.