Этот «боярин хитрый, искательный, велеречивый», как его аттестует Карамзин, набрал такую силу, что немногие из князей могли потягаться с ним в мощи. Собственно, он стал ровней князьям, и это они сами признавали. Достаточно вспомнить, что одну из своих дочерей Всеволожский сосватал за князя Юрия Тверского, другую — за Андрея Радонежского, удельного князя не из последних.

Правда, за два года до поездки в Орду с Иваном Дмитриевичем случился небольшой казус. В пределы княжества вторглось ордынское войско, желающее малость пощипать переживших мор москвичей. Сначала они осадили Галич, но старый вояка Юрий Звенигородский легко отбился. Тогда орда ушла к Костроме, с ходу взяла город, и, качественно почистив его от ценностей и главного товара — людишек, покатилась вниз по Волге. В погоню были посланы Васины дядьки, Андрей и Константин «и с ними Иван Дмитреевич, с своими полки». Погоня «доидоша» до Нижнего Новгорода, но за татарами так и не «угонивши». Там, в Нижнем, Всеволожский и уговорил князей вернуться — мол, не угнались, так не угнались, дело житейское, сами знаете — не в первый раз.

На беду предводителей похода, с ними был еще один князь. Очень молодой, но уже очень амбициозный. Звали его Федор Давидович Пестрый. Один из последних удельных стародубских князей, перешедших на службу в Москву, сын удельного князя стародубского Давида Андреевича Палицы. Федору решение бесславно повернуть назад совсем не понравилось. Он столковался со своим другом, воеводой Федором Константиновичем Добрынским, и они решили действовать на свой страх и риск. Юноши отстали от отступающего войска и,«утаивься у князей да у воевод, и своими полки погнаша за татары, и угониша да их биша, татар и бесермен, и полон весь отняша, а царевича и князя Али-бабы не догониша» . Несмотря на то, что предводитель набега со звучным именем Али-баба ушел, все-таки молодые самовольники сделали главное — спасли от рабства «полон», русских пленников. В итоге осторожному Всеволожскому достались лишь насмешки, а двум юным героям, говоря словами летописца,«при животе честь, а по смерти вечная память» .

Между прочим, «при животе честь» князь Федор Пестрый заслужил еще не раз. Спасение пленных — это лишь первая громкая победа этого юноши, ставшего одним из самых известных полководцев своего времени. Жизнь его была очень долгой, и особенно ярко воинское дарование Пестрого проявилось уже в преклонные годы, во времена правления сына нашего Васеньки — великого Ивана III. Любители современной прозы, кстати, прекрасно с ним знакомы — князь Пестрый является одним из героев прекрасного романа Алексея Иванова «Сердце Пармы».