Setelah menemukan anggota baru, Dream Theater tidak segera mulai bekerja pada materi baru. Fans di seluruh dunia, yang tergabung di YtseJam Mailing List (bentuk komunikasi yang paling populer antara penggemar Dream Theater pada saat itu), mulai memberikan tekanan pada band untuk segera merilis ulang lagu "A Change of Seasons", yang telah ditulis pada tahun 1989 dan dimaksudkan untuk menjadi bagian dari album Images and Words, (tetapi dengan durasi hampir 17 menit, dianggap terlalu panjang untuk penempatan album studio), yang telah sering dimainkan secara live, dan terus merevisinya pada tahun-tahun menjelang 1995.
Petisi ini berhasil, dan band masuk ke "BearTracks Studios" di New York pada Mei 1995 untuk menulis ulang dan merekam lagu yang akhirnya menjadi 23 menit panjangnya, dengan Derek Sherinian yang memberikan kontribusi signifikan terhadap lagu tersebut. Band ini merilis "A Change of Seasons" sebagai EP bersama dengan koleksi lagu penutup dari pertunjukan live yang direkam di Ronnie Scott Jazz Club di London awal tahun 1995.
Judul lagu, direkam di BearTracks Studios di New York, termasuk sampel audio dari film "Dead Poets Society" tahun 1989 dan kutipan dari puisi Robert Herrick, "To the Virgins, to Make Much of Time". Pada awalnya akan dirilis pada tahun 1992 dalam album Images and Words. Lirik ditulis oleh drummer Mike Portnoy, tidak terinspirasi oleh film, melainkan oleh kematian ibunya. A Change of Seasons juga merupakan album pertama Dream Theater yang menampilkan Derek Sherinian pada keyboard.
A Change of Seasons adalah album mini yang diproduseri oleh David Prater, Dream Theater. Daftar lagu yang ada di dalam album ini adalah :
- A Change of Seasons
- Funeral for a Friend/Love Lies Bleeding
- Perfect Strangers
- Led Zeppelin Medley
- The Big Medley
Setelah menjalankan konser singkat dan istirahat sejenak, band ini merilis CD Natal khusus melalui fans club resmi mereka, yang terdiri dari trek langka yang direkam pada awal-awal tahun band ini. Mereka terus merilis sebuah CD fans club baru setiap Natal sampai tahun 2005.
Sementara itu, ada beberapa perubahan pada EastWest, dan penghubung utama Dream Theater pada label dipecat. Akibatnya, tim baru di perusahaan tidak terbiasa berhubungan dengan Dream Theater, dan mereka menekan Dream Theater untuk menulis sebuah album yang lebih mudah didengar. Pada pertengahan 1997, mereka masuk studio untuk menulis album berikutnya. Selain menekan band untuk mengadopsi suara yang lebih menjual, EastWest merekrut penulis/produser Desmond Child agar bekerja sama dengan Petrucci untuk memoles lirik lagu "You or Me". Seluruh anggota band menulis ulang lagu, dan Desmond Child juga memunculkan dampak yang nyata pada album, dengan pergeseran ke arah komposisi yang lebih "radio-friendly".
Dream Theater telah menulis materi hampir dua CD, termasuk lanjutan untuk Images and Words "Metropolis-I: The Miracle and The Sleeper" yang panjangnya hampir 20 menit. Pihak label, bagaimanapun juga tidak mengizinkan peluncuran album ganda karena merasa bahwa durasi 140 menit tidak akan diterima dengan baik oleh masyarakat umum. James LaBrie juga merasa bahwa CD harus satu disk. Lagu-lagu yang tidak terpakai kemudian dirilis di YtseJam Records dengan judul Falling into Infinity Demos.
Materi yang terpakai, dirilis sebagai album Falling into Infinity, yang menerima sambutan beragam dari fans yang lebih akrab dengan suara band sebelumnya. Sementara album ini terdengar kurang progresif. Trek seperti "Hollow Years" dan "You Not Me" membawa nuansa baru pada lagu Dream Theater. Secara keseluruhan, album ini menuai kekecewaan. Meskipun Portnoy tidak berbicara secara terbuka pada saat itu, ia kemudian mengungkapkan dalam DVD dokumenter 5 Years in a Livetime pada tahun 2004, bahwa ia telah begitu putus asa selama periode tersebut dan dia telah menganggap Dream Theater bubar sama sekali.
Selama "Touring into Infinity" ke Eropa, dua konser telah direkam untuk album live berjudul Once in a LIVEtime, di Perancis dan Belanda. Album ini dirilis sekitar 1998 hampir bersamaan dengan rilis video 5 Years in a Livetime, yang meliputi tahun dari kepergian Kevin Moore hingga promo tur Falling into Infinity.