Завоеванный Суперкубок стал последним на данный момент серьезным трофеем «Лидса». В первом сезоне Премьер-лиги «Лидс» занял 17-е место, а в розыгрыше Лиги чемпионов дошел до второго раунда, где уступил шотландцам из «Рейнджерса» (дважды по 1:2). В первом раунде англичане прошли немецкий «Штутгарт», проиграв выездной матч со счетом 0:3, а потом победив дома (4:1) и в нейтральной Барселоне (2:1). Эрик Кантона в этом сезоне покинул коллектив (его за 1,2 миллиона фунтов купил «Манчестер Юнайтед»).

В сезонах 1993/1994 и 1994/1995 «Лидс» дважды был пятым, а в сезоне 1995/1996 – тринадцатым, но зато смог дойти до финала Кубка Футбольной лиги. В решающем матче, который состоялся 24.03.1996, «белые» со счетом 0:3 проиграли «Астон Вилле».

В этом матче цвета «Лидса» защищали: Джон Лукич, Гари Келли, Лукас Радебе (Пер Томас Бролин), Дэвид Уэзеролл, Джон Пембертон, Гари Спид, Карлтон Ллойд Палмер, Марк Стюарт Форд (Брайан Кристофер Дин), Гари Макаллистер (капитан), Эндрю («Энди») Дэвид Грэй, Тони Йебоа. В запасе остался полузащитник сборной Северной Ирландии Найджел Уортингтон («Шеффилд Уэнсдей»).

В розыгрыше Кубка УЕФА сезона 1995/1996 англичане прошли только «Монако» (3:0, 0:1), после чего были биты голландцами из эйндховенского ПСВ (3:5, 0:3).

Среди новичков команды отметим таких футболистов, как защитник из южноафриканского клуба «Кайзер Чифс» Лукас Валери Нтуба Радебе по прозвищу «Вождь», нападающий Брайан Дин из «Шеффилд Юнайтед» (его трансфер обошелся клубу в 2,9 миллиона фунтов), полузазащитник Карлтон Палмер из «Шеффилд Уэнсдей» (2, 6 миллиона), форвард сборной Ганы Энтони («Тони») Йебоа, прибывший из франкфуртского «Айнтрахта», швед Томас Бролин, который в качестве свободного агента пришел из итальянской «Пармы», 17-летний левый вингер из австралийского клуба «Маркони Стэллионс» Харри Кьюэлл и молодой ирландский защитник из клуба «Хоум Фарм» Иан Патрик Харт.

В июле 1996 года в команде появился вратарь Найджел Мартин из «Кристал Пэлас», за которого выложили 2,25 миллиона фунтов. И не прогадали. Тогда же в «Чарльтон Атлетик» за 2,6 миллиона приобрели центрального полузащитника Ли Бойера, а из «Ливерпуля», совершенно бесплатно, пришел звездный ветеран Иан Раш.

Были и потери. Еще в марте 1995 года в «Ковентри Сити» отправился Гордон Страхан (в 1989–1995 провел за «павлинов» 244 матча и забил 45 голов), а в июле того же года в «Болтон» ушел Крис Фэйрклаф (240/23, 1989–1995). Летом 1996 года в «Эвертон» за 3,5 миллиона продали Гари Спида (311/57, 1988–1996), в «Арсенал» вернулся доигрывать Джон Лукич (430, 1978–1983, 1990–1996), а «Ковентри Сити» за 3 миллиона купил Гари Макаллистера (1990–1996, 294/45). Через год в «Торино» уехал Тони Дориго (208/5, 1991–1997), а в июле 1998 года в «Рейнджерс» перешел Род Уоллес (256/66, 1991–1998).

В сентябре 1996 года Говард Уилкинсон покинул коллектив, а новым тренером «Лидса» стал Джордж Грэм, проработавший с командой чуть более двух лет, после чего сдал пост своему бывшему ассистенту – Дэвиду О’Лири. Произошло это событие 01.10.1998. Сезон 1998/1999 «Лидс» завершил на 4-м месте, а нидерландский форвард «павлинов» Джимми Флойд Хассельбайнк, прибывший из португальской «Боавишты», забил 20 мячей.

На стыке веков ирландскому специалисту удалось создать агрессивную, страстную, дерзкую и немного хулиганскую (ну какой же «Лидс» без хулиганов и дебоширов?!) команду, составленную в основном из молодых футболистов. О’Лири привил своему «детскому саду», за которым присматривали опытные Мартин, Бойер и Бэтти, особый командный дух, а также незамысловатый, но крайне эффективный стиль игры, основанный на скоростных атаках, сочетающихся с длинными передачами. И эта тактика приносила «Лидсу» успех. В сезоне 1999/2000 подопечные О’Лири переместились в чемпионате Англии на 3-е место и вышли в полуфинал Кубка УЕФА, где по итогам двух матчей уступили турецкому «Галатасараю» (0:2, 2:2; с эими поединками связано убийство накануне стамбульского матча двух болельщиков «Лидса»).

Еще через год, заняв в чемпионате 4-е место, «Лидс» добирается уже до полуфинала Лиги чемпионов, где на пути англичан встала испанская «Валенсия» (0:0, 0:3). В сезонах 2001/2002–2003/2004 лучшим бомбардиром «Лидса» был австралиец Марк Видука, купленный у «Селтика» за 6 миллионов фунтов.

В основном составе «Лидса» в сезонах 1999/2000 и 2000/2001 играли: Найджел Мартин, Эрик Бакке (из клуба «Сонндал», провел 27 матчей за сборную Норвегии), Дэвид Бэтти, Ли Бойер, Майкл Бриджес («Сандерленд»), Иан Харт, Даррен Хакерби («Ковентри Сити»), Гари Келли, Харри Кьюэлл, Стивен Макфэйл, Дэнни Миллз («Чарльтон Атлетик»), Лукас Радебе, Алан Смит, Джейсон Уилкокс («Блэкберн Роверс»), Джонатан Вудгейт, Оливье Дакур («Ланс», провел 21 матч за сборную Франции), Рио Фердинанд («Вест Хэм Юнайтед»), Робби Кин («Интера» Милан), Доминик Маттео («Ливерпуль»), Пол Робинсон, Марк Видука, Майкл Дюберри («Челси»).

В конце июня 2002 года Дэвид О’Лири покидает команду, а его место занимает Терри Венейблс. По итогам сезона 2003/2004, заняв 19-е место, «Лидс Юнайтед» покидает Премьер-лигу, а по итогам сезона 2006/2007 – и Чемпионшип. Причиной тому стали серьезные финансовые трудности и накопившиеся долги (более 80 миллионов фунтов было истрачено за последние несколько лет на трансферы и зарплату футболистам) и, как следствие, распродажа ведущих игроков.

Среди тех, кого пришлось продать, оказались Алан Смит (228 матчей, 56 голов, 1998–2004), Джонатан Вудгейт (142/4, 1997–2003), Иан Харт (288/39, 1995–2004), Харри Кьюэлл (242/63, 1995–2003), Ли Бойер (265/55, 1996–2003), Марк Видука (166/72, 2000–2004), Пол Робинсон (119/1, 1997–2004), Робби Кин, Рио Фердинанд, Робби Фаулер, Аарон Леннон, Джеймс Милнер и другие. Покинули команду также Лукас Радебе (262/3, 1994–2004), Дэнни Миллз (141/4, 1999–2004) и Доменик Маттео (146/4, 2000–2004).

Осенью 2004 года с молотка ушел стадион «Элланд Роуд» и тренировочная база клуба. Стадион купила компания «Teak Commercial Ltd», зарегистрированная на Британских Виргинских островах. «Лидс» тут же арендовал арену на 25 лет с опцией о возможном выкупе за сумму всех арендных платежей, умноженных на некоторый коэффициент. С сезона 2010/2011 «павлины» вновь выступают в Чемпионшип.