Группа решила переписать 20-минутную композицию с новым участником группы в целый концептуальный альбом, идея которого вращалась вокруг таких тем, как реинкарнация, убийство и предательство. Процесс записи проводился в тайне. Единственное, что знали фанаты, — это список песен, который стал известен вопреки желанию участников Dream Theater, а также дату выхода альбома. Никто не знал ни названия альбома, ни чего-то о музыке, ни того, что альбом будет концептуальным. В 1999 году был выпущен альбом «Metropolis Pt. 2: Scenes from a Memory», который был признан самым лучшим альбомом группы как фанатами, так и критиками, несмотря даже на то, что он достиг только 73 строчки в хит-параде Billboard 200.

Тур, который последовал за выходом альбома, включал в себя больше стран, чем группа когда либо посещала ранее. Этот тур занял больше года. Для специального шоу в Roseland Ballroom в Нью-Йорке был нанят актёр Кент Бродхарст для исполнения роли гипнотерапевта. В этом же концерте был церковный хор под руководством соул-певицы Терезы Томасон, которые присутствовали в качестве приглашённых музыкантов в альбоме. Этот концерт был последним из запланированных шоу в туре по Северной Америке и был записан для первого DVD группы. Концерт был издан на DVD под названием «Metropolis 2000» в начале 2001 года. Немного погодя после выпуска видео группа анонсировала, что скоро будет выпущена аудио версия концерта, которая будет включать в себя весь четырёхчасовой концерт (многое было вырезано из DVD версии из-за нехватки места на носителе).

. Альбом был незамедлительно отозван, но многие копии остались у коллекционеров как исключительная часть истории Dream Theater. Альбом был переиздан с изменённой обложкой.

После всего Dream Theater снова начали сочинение и запись шестого студийного альбома в BearTracks Studios. Через четыре года после просьбы у EastWest Records дать разрешение на запись двойного альбома, они наконец получили его. Новый альбом назывался «Six Degrees of Inner Turbulence» и включал в себя два диска. Первый диск содержит пять песен, длительностью от 6 до 14 минут. Второй диск содержит одну песню, длительностью в 42 минуты, которая разделена на 8 частей. На данный момент это самая длинная из всех когда либо записанных песен Dream Theater.

«Six Degrees of Inner Turbulence» был хорошо принят как критиками, так и прессой. Он был наиболее рекламируемый из всех альбомов Dream Theater со времён «Awake». В течение следующих полутора лет группа гастролировала по всему миру с концертами, на некоторых из которых были сыграны каверы на альбомы других групп.

В завершении тура и некоторых сайд-проектов, Dream Theater начали запись альбома под названием «Train of Thought», который был записан не более чем за три недели и стал самым тяжёлым, мрачным и метал-ориентированным за всю предыдущую историю группы.

Альбом был успешно принят критиками, но вызвал серьёзные разногласия среди фанатов между теми, кто больше ценил музыку Dream Theater за мелодичную прог-роковую составляющую и теми, кто воспринимал коллектив прежде всего как метал-группу.

Следующим шагом стал выпуск DVD и CD версий концерта, который был записан в знаменитом Nippon Budokan Hall в Токио, в рамках мирового тура в поддержку альбома «Train of Thought». Альбом под названием «Live at Budokan» был выпущен 5 октября 2004 года.

Octavarium (2005-06)

По завершении тура 2004 года, Dream Theater начали запись своего восьмого альбома в студии The Hit Factory в Нью-Йорке. Dream Theater оказалась последней группой, записывающейся на этой знаменитой студии, поскольку после записи студия была закрыта. Альбом под названием Octavarium был выпущен 7 июня 2005 года. Среди восьми песен есть продолжение серии песен Майка Портного об обществе Анонимных Алкоголиков (в «Octavarium» это песня «The Root of All Evil», в которой заключены шаги 6-7 из 12-шагового плана). Заглавная песня «Octavarium» за 24 минуты перебирает различные музыкальные стили. Как практически каждый альбом группы, Octavarium был по-разному оценен фанатами и был объектом для оживлённых споров. Так, некоторые фанаты думают, что у группы слишком явно «торчат из рукавов» их музыкальные пристрастия: например, песня «Never Enough» сравнивается с песней Muse «Stockholm Syndrome», а «I Walk Beside You» — с творчеством группы U2, кроме того, простота и мелодичность таких песен альбома как «The Answer Lies Within» и «I Walk Beside You» вызвала со стороны некоторых консервативных фэнов группы обвинения в том, что группа, из коммерческих соображений упрощает своё творчество, пытаясь тем самым подстроится под радио-формат. Octavarium стал последним альбомом по контракту с Elektra Records, и группа покинула лейбл.