Именно благодаря своей неразумной трансферной политики Дэвид Платт стал одним из самых нелюбимых болельщиками персон клуба. На него фанаты возложили всю ответственность за ряд неудачных многомиллионных трансферов. Вследствие клуб ещё больше погряз в долгах, а качество игры оставляло желать лучшего. В июле 2001 года Платт стал тренером молодёжной сборной Англии, передав команду начинающему менеджеру Полу Энтони Харту (в 1983–1985 годах он играл за «лесников» на позиции защитника).

Харт на тренерском поприще успехов с «Форест» не добился и в феврале 2004 года его сменил ирландец Джозеф («Джо») Патрик Киннэйр (часто – Киннир). «Лесники» находились в нижней части турнирной таблицы, но до конца сезона 2003/2004 Киннэйру удалось вытащить клуб на безопасное 14-е место. Новый наставник надеялся на следующий год выйти с «лесниками» в Премьер-лигу, но уже со старта команда играла неудачно и спустилась в самый низ турнирной таблицы. К 23-у туру «Ноттингем Форест» одержал всего 4 победы, и 16.12.2004, после домашнего поражения со счётом 0:3 от «Дерби Каунти» Киннэйр подал в отставку. Временно исполняющим обязанности тренера до конца сезона стал Мик Харфорд, но ему не удалось спасти клуб от вылета из Чемпионшип.

Так «Форест» стал первым клубом Европе, который, имея в активе победы в еврокубках, докатился до третьего по значимости дивизиона национального первенства (Первая Лига), где провел сезоны 2005/2006–2007/2008. С января 2005 по февраль 2006 года генеральным менеджером «Ноттингем Форест» был Гари Мегсон, а в мае 2006 года тренерское кресло занял бывший защитник сборной Шотландии Колин Колдервуд, в сезоне 2000/2001 проведший несколько матчей в составе «Форест».

Старт Колдервуда получился удачным – по итогам сезона «лесники» заняли четвёртое место в турнирной таблице, но в играх плей-офф за выход в Чемпионшип потерпели поражение от «Йовил Таун». Следующий футбольный год принёс Колдервуду и его «Ноттингему» успех, хотя всё начиналось достаточно неудачно – на старте кампании «Форест» не знали вкуса побед шесть матчей, за что Колин подвергался жёсткой обструкции со стороны фанатов и журналистов. Однако затем набравшая ход команда стала сокрушать одного соперника за другим, всего лишь один раз потерпев поражение в пятнадцати играх.

После этого «лесники» провели ряд неровных матчей, и за семь поединков до окончания футбольного года были в девятиочковом отставании от зоны автоматического выхода в Чемпионшип. Тем не менее, «Ноттингем» в оставшихся семи матчах смог выиграть шесть раз и добился автоматического выхода в Чемпионшип, заняв в турнире 2-е место (+22=16–8, мячи 64–32). «Донкастер Роверс» и «Карлайл Юнайтед» отстали на два очка. Колдервуд за подобный спурт своей команды удостоился приза «Лучшего тренера» апреля 2008 года.

Ворота команды в этом сезоне защищал Пол Дэниел Смит (142, 2006–2012), выступавший прежде за «Брентфорд» и «Саутгемптон», в защите играли пришедший из «Престона» воспитанник «Ноттс Каунти» Кельвин Джеймс Уилсон (134, 2007–2011), Люк Чемберс из «Нортгемптон Таун» (229/21, 2007–2012), воспитанник клуба Уэсли («Уэс») Натан Морган, защищавший цвета национальной сборной Ямайки (402/14, 2002–2012), а также капитан команды Иан Брекин из «Уиган Атлетик» (161/14, 2005–2009) и Джулиан Ллевелин Беннетт из «Уолсолл» (110/8, 2006–2011).

В середине поля трудились Джеймс Перч из молодежной академии «Форест» (220/14, 2004–2010), прибывший из «Сток Сити» игрок сборной Шотландии Кристиан («Крис») Аррон Коммонс (159/38, 2004–2008), Кристофер («Крис») Дэвид Коэн из «Йовил Таун» (255/15, 2007–2014), игрок сборной Северной Ирландии Сэмьюэл («Сэмми») Гари Клингэн из «Вулверхэмптона» (96, 2006–2008), воспитанник клуба Льюис Шей Макгуган (229/44, 2006–2013), бывший капитан сборной Северной Ирландии и «Селтика» Нил Фрэнсис Леннон (22, 2007–2008). Среди нападающих выделялись игрок сборной Ганы Мануэль Джуниор Агого из «Бристоль Роверс» (75/23, 2006–2008), Натан Тайсон из «Уиком Уондерерс» (211/42, 2005–2011) и Грант Холт из «Рочдейл» (108/25, 2006–2008).

Повышение в классе не принесло «лесникам» ничего кроме разочарования – к декабрю 2008 года клуб смог одержать лишь четыре победы и в конце месяца Колдервуд был уволен со своего поста, а его место занял другой шотландец – Билли Дэвис, проработавший с клубом до июня 2011 года.

После этого «Ноттингем Форест» тренировали Стив Макларен, Стив Коттерилл, Шон Майкл О’Дрисколл, Алекс Маклиш, а с февраля 2013 года вновь Билли Дэвис. Лучший результат, показанный клубом после возвращения в Чемпионшип, – 3-е место в сезоне 2009/2010 и 6-е в сезоне 2010/2011.