В 1524 году — воевода на Угре.
В 1528 году с братом Иваном Шуйским намеревался сделать карьеру («отъехать») у князя Юрия Дмитровского. Воевода полка правой руки в войске Василия Шуйского Немого и Ивана Васильевича Шуйского в походе к Нижнему Новгороду.
В 1534 году после смерти Василия III повторно собирался «отъехать». По приказу Елены Глинской брошен в тюрьму и освобождён лишь после её смерти в 1538 году.
Наместник Новгорода (1539-1540) и Пскова (1540). Проявил себя жестоким и алчным администратором. Вернувшись в Москву, возглавил борьбу за влияние при дворе.
После смерти Ивана Васильевича Шуйского и убийства Ивана Бельского встал во главе боярского правительства в мае 1542 года.
В сентябре 1543 года Андрей Шуйский и его единомышленники на глазах митрополита Макария и 13-летнего великого князя Ивана Васильевича, избили боярина Фёдора Воронцова.
29 декабря 1543 года великий князь Иван Васильевич, обвинив Шуйских в том, что они «безчиние и самовольство чинят», «велел его предати псарям, и псари взяша и убиша его». Наместник московский «лежал наг в воротех два часа». Смерть Андрея Михайловича положила конец влиянию Шуйских на большую политику.