Если Мишин заложил технику фигуриста, то Тарасова стала тем тренером, который смог раскрыть его артистический потенциал. В пост-олимпийском сезоне Ягудин выиграл 11 стартов из 13, в которых участвовал. На чемпионате мира Алексей чисто исполнил четверной тулуп и получил от одного из судей оценку 6.0 за технику и шесть оценок 5.9 за артистизм. В середине следующего сезона Ягудин получил травму. Но и она не смогла помешать ему стать первым в истории России фигуристом, который три раза подряд выиграл мировое первенство.
В это время родились иконические «голливудские» программы Ягудина, поставленные под музыку из известных фильмов. Одна из них «Гладиатор» — произвольная программа сезона 2000/2001 года. Новый чемпионат мира — новая травма. После короткой программы врачи предписали фигуристу сняться, но он все равно вышел на лед. Через боль Алексей боролся до конца, но стал только вторым — в первый и в последний раз уступив титул бывшему товарищу по тренерскому штабу — Евгению Плющенко.
Второй олимпийский сезон дался Ягудину непросто. В начале года он даже работал со спортивным психологом, борясь с мыслями уйти из спорта. К счастью всех любителей фигурного катания, этого не произошло, и мир стал свидетелем пика спортивной карьеры атлета. Его программы этого сезона — «Зима» и «Человек в железной маске» — вошли в негласный золотой фонд фигурного катания. «Зиму» часто называли эталоном постановки короткой программы. Алексей стал первым олимпийским чемпионом, выполнившим два четверных прыжка в одной программе. Ягудин получил высочайшие оценки за технику и артистизм, включая четыре оценки 6.0. На чемпионате мира Алексей превзошел и это свое достижение: за «Зиму» он получил шесть «шестерок» — пять за артистизм и одну за технику.
Выиграв Олимпиаду Ягудин собрал так называемый «большой шлем» фигурного катания: золото Игр, чемпионатов мира и континента, финала Гран-При. Удивительно, но при этом за всю свою карьеру Ягудин ни разу не стал чемпионом России, четыре раза уступив титул Плющенко. Почти вся спортивная карьера Ягудина — дуэль. Противостояние двух российских титанов, практически ровесников развивало и двигало вперед мировое фигурное катание на рубеже веков. Но если Плющенко задержался в элите фигурного катания еще на десятилетие, то Ягудину пришлось распрощаться с большим спортом совсем скоро.
Послеолимпийский сезон Ягудин начал с побед, но старая травма бедра дала о себе знать, и Алексей впервые в жизни снялся с соревнований после исполнения короткой программы. Зрители провожали фигуриста овациями. В 2013 году спортсмен официально объявил о завершении карьеры.
Ягудин, любимец публики по всему миру, хоть и владел четверными прыжками, прежде всего запомнился своими дорожками — скоростными, с замысловатой кривой и большим количеством связующих элементов, сложной хореографией. После завершения карьеры Ягудин, конечно же, был приглашен в престижное ледовое шоу «Stars on Ice», где выступал с облегченным набором элементов и на обезболивающих. После операции на тазобедренном суставе Алексей воодушевленно говорил в интервью об идее вернуться в любительский спорт. Но, как оказалось, боль отступила только на время и с мечтой пришлось расстаться.
Сейчас Ягудин является постоянным комментатором трансляций фигурного катания и ведет свое собственное шоу на спортивном канале, участвует в ледовых шоу и телевизионных проектах. В 2016 году Ягудин женился на фигуристке Татьяне Тотьмяниной — олимпийской чемпионке 2006 года в парном катании. Алексей и Татьяна — родители двух девочек, Елизаветы и Мишель.