Затем начались поездки послов в Москву и Вильно. В 1493 г. в ходе одной из «челночных» поездок московский посол дворянин Загряжский привез грамоту со странным требованием передачи Москве ряда русских городов. Сенсацией в ней стал новый титул Ивана III. До сих пор в верительных грамотах Казимиру Иван III писал так: «От Великого князя Ивана Васильевича Казимиру королю польскому и Великому князю Литовскому послами есмо». Теперь же грамота начиналась: «Иоанн, Божьею милостию государь всея Руси и Великий князь Владимирский, и Московский, и Новгородский, и Псковский, и Тверской, и Югорский, и Болгарский, и иных, Великому князю Александру Литовскому».

Итак, впервые Великий князь Московский назвал себя «государем всея Руси». Что же произошло? Да ничего, кроме того что военная мощь Литвы в тот момент была ослаблена, а силы Ивана III велики. Кроме того, Литве угрожал союзник Московского князя крымский хан Менгли-Гирей. Иных аргументов у Ивана III не было. Он даже не стал рассуждать о преемственности московских князей древнерусским киевским князьям. То ли в силу неубедительности сей посылки, то ли потому, что сам Иван с боярами имел весьма смутное представление о Киевском государстве. Послу же был дан такой наказ: «Если спросят его: для чего князь Великий назвался государем всея Руси; прежде ни отец его, ни он сам к отце государя нашего так не приказывали? То послу отвечать: государь мой со мной так приказал, а кто хочет знать зачем, тот пусть едет в Москву, там ему про то скажут».

В январе 1494 г. в Москву едут большие литовские послы. После долгих препирательртв литовские послы уступили Ивану III большую часть спорных земель, и, главное, в договорной грамоте Иван III был написан государем всея Руси, Великим князем Владимирским, Московским, Новгородским, Псковским, Тверским, Югорским, Пермским, Болгарским и иных.

По окончании переговоров Иван III объявил, что соглашается выдать дочь за Александра, если только, как говорили послы и ручались головой, неволи ей в вере не будет.

В январе 1495 г. новые послы приехали за невестой – московской княжной Еленой. В Вильно венчал Александра и Елену католический епископ, но русский поп Фома, приехавший с Еленой, стоял рядом и громко молился. Александр и вельможные паны просили его помолчать, но Фома не унимался до конца церемонии.

Мир с Литвой просуществовал всего пять лет, а затем литовские паны нарушили его. Но на сей раз не напали на Московское государство, а, наоборот, попросились на службу к Ивану III. И полбеды, если бы они попросту драпанули через границу, так они попросились в Московское государство вместе со своими уделами.

Первым к Ивану III подался в 1499 г. князь Семен Иванович Вельский. Семен Иванович был правнуком Великого Литовского князя Ольгерда, то есть по отцовской линии он был литовцем. Сын Ольгерда Владимир в конце XIV века стал киевским князем, а его второй сын Иван получил в удел город Белев. Этот Иван и стал родоначальником князей Вельских.

Семен Вельский прибыл в Москву, «бил челом Великому князю, чтоб пожаловал, принял в службу и с отчиной». Причиной своего поступка Вельский назвал притеснения православных в Литве – «терпят они в Литве большую нужду за греческий закон».

Иван III принял Вельского и послал сказать Александру: «Князь Вельский бил челом в службу; и хотя в мирном договоре написано, что князей с вотчинами не принимать, но так как от тебя такого притеснения в вере и прежде от твоих предков такой нужды не бывало, то мы теперь князя Семена приняли в службу с отчиною». Вельский тоже послал Александру грамоту, где слагал с себя присягу по причине принуждения к перемене веры.