22.05.1999 на «Уэмбли» в составе «Ньюкасла» играли: Стивен («Стив») Алан Харпер (пришел в 1993 году из молодежной деревенской команды «Сиэм Ред Стар» Изингтон), Энди Гриффин, Лоран Шарве из французского «Канна», Николас Дабизас, Дидье Арсен Марсель Доми из «Пари Сен-Жермен», Роб Ли, Дитмар Хаманн из «Баварии» (Дункан Фергюсон из «Эвертона»), Гэри Спид, полузащитник сборной Перу Нолберто Альбино Солано из «Бока Хуниорс» (форвард сборной Хорватии Силвио Марич из «Динамо» Загреб), Темури Кецбая (Стивен Гласе из «Абердина»), Алан Ширер (капитан). Самой заметным дебютантом был Нолберто Солано, проведший в итоге за «сорок» 315 матчей, и забивший 48 голов (1998–2004, 2005–2007).

Рюд Гуллит проработал в коллективе ровно год, а в сентябре 1999 года, после серии неудачных матчей, неоправданных приобретений и конфликта с главной звездой клуба Аланом Ширером и капитаном Робом Ли, голландец подал в отставку, а новым главным тренером «сорок» стал легендарный сэр Роберт («Бобби») Уильям Робсон, проработавший с командой до августа 2004 и создавший уникальный коллектив исполнителей.

В сезоне 2001/2002 «Ньюкасл» поднялся на 4-е место (до этого, два сезона подряд «Сороки» занимали 11-е место), а в сезоне 2002/2003 – на третье. При этом подопечные Робсона смогли пройти во второй групповой этап Лиги чемпионов. В следующем году «Ньюкасл» был пятым в чемпионате и дошел до полуфинала Кубка УЕФА, где по итогам двух матчей уступил марсельскому «Олимпику» (0:0, 0:2).

Болельщики и игроки любили и безгранично уважали харизматичного Робсона за талант, любовь к футболу, энергичность и энтузиазм, а также за его эксцентрическую натуру. При Робсоне в «Ньюкасле» заиграли Кирон Кортни Дайер, купленный у «Ипсвича» за 6 миллионов фунтов (250/36, 1999–2007), Аарон Уильям Хьюз (278/7, 1997–2005), Оливье Бернар из лионского «Олимпика» (145/6, 2000–2007), Джейрмейн Энтони Дженас, которого приобрели за 5 миллионов у «Ноттингема» (151/12, 2002–2005), француз Лоран Робер, за которого «Пари Сен-Жермен» получил 9,5 миллионов (181/32, 2000–2005), воспитанник клуба Фолувашола («Шола») Сэмми Амеоби из молодежной сборной Англии, с 2012 года выступающий за сборную Нигерии (388/77, 2000–2014), Эндрю («Энди») Джеймс О’Брайен из «Брэдфорд Сити» (171/7, 2001–2005), купленный за 6,0 миллионов у «Ковентри Сити» Крейг Дуглас Беллами (128/43, 2001–2005), Тайтус Малачи Брамбл из «Ипсвича» (157/7, 2002–2007) и др. После четырех неудачных стартовых матчей сезона 2004/2005 сэр Бобби был уволен.

После ухода Робсона тренерская чехарда (Грэм Сунесс, Гленн Рёдер, Сэм Эллардайс и др.) продолжалась в течение нескольких лет, что не приводило ни к чему хорошему. В августе 2005 года «сороки» купили у мадридского «Реала» Майкла Оуэна за рекордные 17 миллионов фунтов. В сезонах 2007/2008 и 2008/2009 восстановившийся от травм Оуэн становился лучшим бомбардиром клуба. Всего форвард провел за «сорок» 79 матчей и забил 30 голов (2005–2009).

Крайне неудачным для «Ньюкасла» выдался сезона 2008/2009. Спустя месяц после начала турнира Кевин Киган (он сенсационно вернулся на пост тренера в середине сезона 2007/2008 и с его именем болельщики связывали надежды на новые успехи), недовольный трансферной политикой клуба, покинул команду (в ответ на этот шаг болельщики устроили серию протестов с требованиями вернуть легенду и сменить владельца), а его место занял Джо Киннейр, при котором «Ньюкасл» опустился в самый низ турнирной таблицы.

В феврале 2009 года Киннер подал в отставку и до конца сезона руководство «Ньюкаслом» было передано Алану Ширеру. В итоге, в конце мая 2009 года «Ньюкасл» покинул Премьер-Лигу. Тогда за команду играли такие известные футболисты как Ники Батт из «Манчестер Юнайтед» (171/5, 2004–2005, 2006–2010 МЮ), воспитанный в клубе защитник Стивен Винсент Тейлор (243/13, 2003–2013), нападающий Обафеми Акинвунми Мартинс, купленный за 10,0 миллионов фунтов у миланского «Интера» (104/35, 2006–2009), полузащитник Дэмьен Дафф из «Челси» (86/6, 2006–2009) и др.

Возвращение «сорок» в элиту английского футбола произошло на следующий же год. Ведущие роли играли в этом сезоне аргентинцы Фабрисио Колоччини из «Депортиво» Ла-Корунья (203/5, 2008–2014) и Хонас Гутьеррес из «Мальорки» (192/11, 2008–2014), испанец Хосе Энрике Санчес из «Вильярреала» (129/1, 2007–2011), Кевин Нолан из «Болтона» (91/30, 2009–2011), Джои Бартон из «Манчестер Сити» (84/8, 2007–2011), Дэнни Гатри (104/9, 2008–2012), Алан Смит (94, 2007–2012), Энди Кэрролл (92/33, 1999–2011), нападающий сборной Дании Петер Лёвенкранс из «Шалке-04» (85/29, 2009–2012), Дэнни Симпсон из «Манчестер Юнайтед» (138/2, 2009–2013), Майк Уильямсон из «Портсмута» (127, 2010–2014) и др. Тренировал тогда команду Крис Хьютон, которого в декабре 2010 года сменил Алан Пардью, подписавший контракт на пять с половиной лет.