Наместник новгородский 1500-06. Командуя новгородскими войсками в 1501, принял участие в походе на Ливонию под общим командованием Даниила Щени, как воевода передового полка. 27 августа около Изборска русское войско потерпело значительное поражение от ливонцев под командованием фон Плеттенберга. Через год 24 ноября 1502 Щеня и Шуйский успешно отразили фон Плеттенберга от Изборска. В 1503 году водил новгородцев на помощь Пскову против ливонцев. В 1504 году ходил из Новгорода в Литву.
Карьерный рост князя Василия при Василии III значительно ускорился. В 1506 году он, несмотря на молодость, получает чин боярина. Как воевода полка правой руки участвовал в Литовском походе 1507. В 1508, как воевода в Вязьме, ходил на помощь к князьям Стародубским. Был во главе боярской комиссии на переговорах с Литвой 1509, новгородский наместник 1510-1514.
Боярин с 1512. Второй воевода в передовом полку в первом Смоленском походе 1512, главнокомандующий в Луках во время второго Смоленского похода 1513. Участник договорной комиссии с Ливонией 1513-14. Стал первым наместником и воеводой Смоленска 1514-17. В 1514 Василий Немой разоблачил заговор смоленских бояр и епископа, намеревавшихся переметнуться на сторону Литвы, перевешал на стенах города изменников-бояр, а епископа выдал государю. Такая деятельность снискала Василию Шуйскому расположение великого князя.
Главнокомандующий в Литовском походе 1515. Во главе войск на Вязьме в 1517. Наместник новгородский 1517-19, владимирский и первый боярин с 1519. Главнокомандующий в походе к Полоцку 1519.
Будучи вторым воеводой в Серпухове и Кашире против крымцев в 1521 потерпел поражение. После поражения в опале до 1522. Во главе "судовой рати" в Казанском походе 1523. Наместник муромский в 1526-27. Во главе войска к Нижнему для войны с Казанью в 1531, под Коломной против крымцев в 1532. Во главе Большого полка в Смоленском походе на Литву 1535.
Умирая, великий князь Василий Иванович именно ему поручил заботиться о своей супруге, о малолетнем сыне (будущем царе Иване IV) и обо всем Московском государстве. Однако после смерти Василия III молодой князь Телепнев-Оболенский сумел отстранить Шуйского от власти, оставив ему почетный чин первого боярина Государевой думы.
В апреле 1538 года умерла великая княгиня Елена Глинская, покровительствовавшая Телепневу-Оболенскому. Телепнев-Оболенский был брошен в тюрьму и, по всей вероятности, уморен голодом. Шуйский получил практически неограниченную власть, однако, желая еще более укрепить ее, женился на двоюродной сестре малолетнего Ивана IV. Василию в то время было более пятидесяти лет. Против Шуйского стал интриговать князь Иван Бельский, к которому примкнули часть придворных бояр и митрополит Даниил. Бельский хотел ослабить власть Шуйских и возвысить при дворе свой род, но Шуйские оказались сильнее. Бельский был посажен в тюрьму, а его приверженцы разосланы по отдаленным деревням.
В ноябре 1538 года Василий Немой умер.