В 1556 году Курбским была одержана новая победа в походе против черемис. По возвращении он назначается воеводою полка Левой руки, стоящего в Калуге для охраны южных рубежей от крымских татар. Затем вместе с Щенятевым Курбский был направлен в Каширу, где принял под командование полк Правой руки.
Начавшаяся война с Ливонией вновь привела Курбского на поля сражений. В начале войны он возглавил Сторожевой полк, а затем, командуя Передовым полком, он участвовал во взятии Нейгауза и Юрьева (Дерпта). Вернувшись в Москву в марте 1559 года, Курбский был направлен на защиту южных границ от крымских татар. Но вскоре начались неудачи в Ливонии, и царь снова вызывает Курбского и назначает его начальствовать над всеми войсками, сражающимися в Ливонии. Новый командующий действовал энергично. Он не стал дожидаться подхода всех русских дружин и первым напал на ливонский отряд под Вейсенштейном (Пайде), одержав победу. Затем он принимает решение дать бой главным силам противника, которые возглавил сам магистр Ливонского ордена. Обойдя основные силы ливонцев по болотам, Курбский не стал ждать. И как писал сам Курбский, ливонцы «яко гордые стояли на широком поле от тех блат (болот), ждущие нас к сражению». И хотя время было ночное, русские войска завязали перестрелку с противником, которая переросла вскоре в рукопашную схватку. Победа снова была на стороне русского оружия.
Дав войску десятидневную передышку, Курбский повел войска дальше. Подойдя к Феллину и спалив предместья, русские войска осадили город. В этом сражении в плен был взят ландмаршал ордена Филипп Шаль фон Белль, который спешил на помощь осажденным. Важный пленник был отправлен в Москву, и с ним Курбский направил письмо царю, в котором просил не казнить ландмаршала, потому что он «муж не токмо мужественный и храбрый, но и словества полон, и остр разум, и добро память имуща». Эти слова характеризуют благородство Курбского, умевшего не только хорошо сражаться, но и с уважением относиться к достойному противнику. Правда, ландмаршалу ордена заступничество Курбского не помогло. По приказу Ивана IV он все-таки был казнен. Да что говорить о командующем войсками противника, когда к тому времени правительство Сильвестра и Адашева пало, и царь казнил одного за другим своих советников, сподвижников и друзей без всякого к тому основания.
Взяв за три недели Феллину, Курбский двинулся сначала на Витебск, где сжег посад, а затем к Невелю, под которым потерпел поражение. Он понимал, что, пока победы были с ним, царь не станет подвергать его опале, но поражения могут быстро привести его на плаху, хотя, кроме сочувствия опальным, никакой другой вины за ним не было.
После неудачи под Невелем Курбский назначается воеводой в Юрьев (Дерпт). Иван IV не упрекает своего командующего за поражение, не ставит ему в вину измену, но Андрей Михайлович чувствует, что тучи сгущаются над его головой. Ранее его на службу звал польский король Сигизмунд-Август, обещая хороший прием и безбедную жизнь. Теперь Курбский всерьез задумался над этим предложением, и 30 апреля 1564 года он тайно бежал в город Вольмар. Вместе с ним ушли к Сигизмунду-Августу приверженцы и слуги Курбского. Польский король принял их очень благожелательно, наградил Курбского поместьями в пожизненное владение, а через год утвердил за ними право наследственной собственности.
Узнав о бегстве Курбского, Иван IV обрушил свой гнев на его родственников, оставшихся в России. Тяжелая участь постигла близких Андрея Михайловича, и как он сам пишет впоследствии, царь «матерь ми и жену и отрочка единого сына моего, в заточении затворенных, троскою поморил, братию мою, единоколенных княжат Ярославских, различными смертьми поморил, имения мои и их разграбил». Дабы оправдать свои действия относительно его родственников, Андрей Михайлович был обвинен в измене царю, в желании лично править в Ярославле и в заговоре с целью отравления жены царя Анастасии. (Понятно, что два последних обвинения были надуманны.)
На службе у короля Сигизмунда-Августа Курбский быстро стал занимать высокие посты. Через полгода он уже воюет против России. С литовцами он ходил к Великим Лукам, защищал Волынь от татар, а в 1576 году, командуя большим отрядом в составе войск Стефана Батория, бился с московскими полками под Полоцком.