Addition of Jordan Rudess and Metropolis Pt. 2: Scenes from a Memory (1999–2000)

In 1997, Magna Carta Records' Mike Varney invited Portnoy to assemble a progressive 'supergroup' to work on an album, which would become the first in a long string of side-projects for the members of Dream Theater. The lineup consisted of Portnoy on drums, Petrucci on guitar, Tony Levin on bass, and keyboardist Jordan Rudess, who had finished with the Dixie Dregs. The band assumed the name Liquid Tension Experiment, and would act as a medium through which Portnoy and Petrucci could once again court Rudess to join Dream Theater. In 1999, he accepted an offer to become the third full-time Dream Theater keyboardist, replacing Sherinian.

With yet another new member, Dream Theater entered BearTracks Studio once again to write and record their next album. As a result of an ultimatum from Portnoy, the label gave the band complete creative control. The follow-up to "Metropolis Part 1", which was written during the Falling Into Infinity sessions (but not used on that album), was taken off the shelf for reworking. They decided to expand the 20-minute song into a complete concept album, with a story revolving around themes such as reincarnation, murder and betrayal. To avoid stirring up the fan base, a tight veil of secrecy enveloped the writing and recording process. The only things fans were privy to prior to its release were a track list that had been leaked against the band's wishes, and a release date. In 1999, Metropolis Pt. 2: Scenes from a Memory was released to high critical acclaim. It was hailed as Dream Theater's masterpiece by many fans and critics alike, despite only reaching #73 on the US album chart.

The album was mixed by David Bottrill, but only a few of his mixes made it on the final album. The bulk was remixed by Kevin Shirley. The rest of the mixes can be heard in the band's official bootleg "The Making of Scenes from a Memory".

A massive world tour followed recording the album, taking over a year to complete, by far their largest to that point. The concerts reflected the theatrical aspect of the album. They played the entire Scenes From a Memory album from start to finish, with a video screen on the back wall of the stage showing a narrative companion to the story of the album. In addition to playing the album in its entirety, the band also played a second set of Dream Theater songs, as well as a few covers and improvisations of old Dream Theater material. For one extra special show, at the Roseland Ballroom in New York City, actors were hired to play characters in the story, and a gospel choir was enlisted to perform in some sections of the performance.

This show, the last North American date of the tour, was recorded for the band's first DVD release. After many technical delays, the DVD, titled Metropolis 2000, was released in early 2001. Shortly after, the band announced that an audio version of the concert, with the entire four-hour long set-list (some of which had to be cut from the DVD to save space), would be released.

The cover for the CD version of the concert, titled Live Scenes from New York, depicted one of Dream Theater's early logos (the Images and Words-era burning heart, modeled on the Sacred Heart of Christ) modified to show an apple (as in "Big Apple") instead of the heart, and the New York skyline, including the twin towers of the World Trade Center, in the flame above it. In an unfortunate coincidence, the album was released on the same date as the September 11 attacks. The album was quickly recalled by the band and was re-released with revised artwork later,though some copies were sold, and have since become rare collectors items for fans