Following a brief tour in support of the A Change of Seasons EP, Dream Theater entered Dream Factory Studios in East Rutherford, New Jersey in early 1996 to begin writing material for a new album. It was their first time writing with keyboardist Derek Sherinian, who replaced Kevin Moore in 1994. Around this time, Elektra Records was exerting pressure on the band to write concise, radio-friendly songs. Consequently, creative conflicts arose, with John Petrucci accepting the label's plea for change and Mike Portnoy fighting against it.

For over a year, Dream Theater wrote songs without being given permission to record them, and at one point became so frustrated that they considered retirement. In March 1997, the band were finally given the go-ahead to record the new album with Kevin Shirley producing. By May, the band had enough material for a double album, but was told to keep it to one disc for budget reasons. As a result, certain songs were not included on the final cut of the album, including "Raise the Knife", "Where are You Now", "Cover My Eyes", "Speak to Me", "The Way It Used to Be", and "Metropolis Pt. 2", the latter of which was later expanded into its own album, with the rest being included on the 1999 fan club CD "Cleaning Out the Closet". Shirley made significant alterations to some of what was left on the album; most notably, he took the middle section out of "Burning My Soul" and turned it into what would become "Hell's Kitchen". Shirley also recommended that the band work with Desmond Child to re-write "You Or Me", resulting in Petrucci being flown down to Florida to work on the song with Child. Following the sessions, the song became "You Not Me".

Actual recording for the album began on June 2 at The Power Station (now Avatar Studios) in Manhattan, New York City. In contrast to the difficult writing and pre-production stages, the band considered the recording sessions trouble free and enjoyable. The album, titled Falling Into Infinity, was completed on July 30. Originally, Petrucci and Portnoy wanted to call it Stream of Consciousness, but the rest of the band rejected the name because they felt it was too pompous (although the phrase "Stream of Consciousness" is found in the song "Lines in the Sand"). Its eventual title was proposed by Petrucci, and its cover art was designed by Storm Thorgerson.