Fans had previously requested the band to make the sequel to the first part of the song "Metropolis—Part I" from Images and Words, but they had not yet been able, nor had they originally intended one to be made. With the sessions for Falling Into Infinity (1997), the band recorded a 21-minute instrumental demo of "Metropolis Pt. 2", but this did not make it onto that album. The demo, which included several musical citations from "Metropolis—Part I" and featured many motifs that would later appear on Metropolis Pt. 2: Scenes from a Memory (most notably the majority of "Overture 1928" and "Strange Deja Vu" and parts of "The Dance of Eternity" and "One Last Time"), was however significantly different from the finished album version in most part.

The band went back to BearTracks Studios in Suffern, New York to record their new album, previously the site of recording for Images and Words (a photograph of Beartracks is featured on the album's back cover, meant to represent the house in the album). After the commercial failure of Falling Into Infinity, their record label gave the band free rein over their new album's direction, which led the band to finally finish the story. The final version of the story became a concept album, dealing with the story of a man named Nicholas and the discovery of his past life, which involves love, murder and infidelity as Victoria Page, and as such was heavily inspired by the 1991 film Dead Again, more so than the original "Metropolis—Part I".

Following the album's release, the band embarked on an extensive world tour, and at a show in New York City the band actually hired actors to perform the narrative elements of the album whilst they played. The performance was recorded and was released in 2001 as the Metropolis 2000 Live DVD. In 2011 the album was released on LP for the first time to celebrate Record Store Day.