The album's release had been delayed numerous times since the announcement on November 16, 2005 that the band was going to "start pulling it all together". In a fan club chat on March 18, 2006, guitarist and main songwriter Michael Romeo said that the album will be "a bit darker—the direction is still the same—for the most part", and went on to say that "the classical stuff was getting to a point where we need to evolve the music a bit. There is still a lot of classic influence in there—not as obvious as '[Out of the] Ashes', say". He went on to suggest that there may be a song or songs on the album themed around the works of H. P. Lovecraft, and that there would be "A big tune on here ... Paradise Lost is the theme as of now", lending rumor to the title of the album.
In August 2006, some preliminary cover art was leaked on the internet, confirming suspicions that the title of the album would be the same as the song "Paradise Lost". This leaked album art, which was initially categorized by the band as only "preliminary" artwork, was later revealed to be the official artwork, with the full panorama (including the back cover) being made available on the official Symphony X website on May 12, 2007.
At one point it was announced that the album would be released in late 2006, but the date was pushed back several times before its final release date of June 26, 2007. On May 12, 2007, "Serpent's Kiss" was made available on the band's Myspace profile. MP3 samples of other tracks from the album were also made available on German record label SPV's website. In addition to the standard jewel case edition, the album was released in two other formats: a special edition with Digipak packaging, which includes a DVD containing 5.1 audio and music videos for "Serpent's Kiss" and "Set the World on Fire"; secondly, a limited edition including a DVD of footage shot by the band throughout its history (a first for the band), available exclusively in f.y.e. stores. When pre-ordered at Newbury Comics, the first 500 copies received a signed CD booklet.