Военная активность русских, а также внутренние проблемы страны заставили Александра Казимировича поспешить с завершением войны. 2 апреля 1503 г. между Россией и Литвой было заключено перемирие сроком на шесть лет. Под власть Ивана III переходила Северская Украина, а также крепости на западном направлении — Дорогобуж, Белая и Торопец. В тот же день было подписано и шестилетнее перемирие с Ливонией, согласно которому стороны возвращались к довоенным границам и обменивались пленными.

Война 1500–1503 гг. принесла победу Ивану III. Однако и Орден, и особенно потерявшее почти треть своей территории великое княжество Литовское не считали итоги войны окончательными. Их правители ждали удобного случая, чтобы возобновить военное противоборство.

Кончина Ивана III породила новые надежды у недругов Руси. Однако наследник грозного "московита" великий князь Василий Иванович твердой рукой взял власть и не допустил каких-либо династических смут. Новый государь был милостив к Шуйскому.

Уже в 1506 г. он получил высший придворный чин — боярина. Однако расположение великого князя следовало укреплять ревностной службой.

Судьба Василия Немого, как и всякого боевого воеводы, была полна переездов с одного места службы на другое. В октябре 1506 г. закончилось его наместничество в Новгороде. Князя ожидали иные края и иные заботы. Весной 1507 г. началась новая война с Литвой. Там после кончины Александра Казимировича 20 августа 1506 г. к власти пришел его брат Сигизмунд, настроенный крайне враждебно по отношению к Москве. Одновременно возникла и опасность нападения крымских татар. Прежний союзник московского государя хан Мухаммед-Гирей резко изменил свою позицию и летом 1507 г. послал своих мурз на южные окраины России. Туда для борьбы с татарами из Москвы были посланы стойкие, испытанные воеводы.

Летом 1507 г. мы встречаем Василия Немого в Серенске — древнем городе-крепости между Калугой и Брянском. Здесь проходила передовая линия русских укреплений, обращенных на юг. Вместе с другими воеводами Шуйский участвовал в отражении набега крымских татар в августе 1507 г. (38, 70). Осенью 1507 г., когда угроза с юга миновала, войска, собранные в верховьях Оки, были направлены на запад, в литовские земли. В этом походе Шуйский командовал полком правой руки.

Весной 1508 г. в Литве начались внутренние распри. Против великого князя Литовского и одновременно короля польского Сигизмунда выступил Михаил Глинский — крупнейший магнат православного вероисповедания. На помощь ему были посланы московские воеводы. Основные события развернулись на территории современной Беларуси. Мятеж Глинского был подавлен, а сам он вынужден был бежать в Москву. К осени 1508 г. литовская армия приблизилась к западной границе России. Василий III спешно укреплял смоленские города.

В эти тревожные месяцы весны и лета 1508 г. Василий Немой возглавлял запасную рать, стоявшую в Вязьме — в ближайшем тылу разгоравшейся войны. Однако в октябре 1508 г. между Василием III и Сигизмундом был заключен "вечный мир". Вскоре Шуйский был отправлен на прежнее место службы — наместником в Новгород.

Новое обострение отношений с Литвой произошло осенью 1512 г. Правительство Василия III предприняло еще одну попытку возвратить Смоленск. Туда двинулась большая рать. Как и прежде, войскам из северо-западных районов страны был дан приказ двинуться на юг — через Холм в направлении Смоленска. В ходе этой кампании Шуйский с новгородцами предпринял вторжение в литовские земли в районе Себежа (54, 507).