Titelblatt der Erstauflage der literarischen Vorlage von John MiltonsParadise LostDigipak CD Edition von Paradise Lost
Am 16. November 2005 kündigte Symphony X den Beginn ihrer Arbeiten zum neuen Album an. In einem Fanclub-Chat verriet Gitarrist und Hauptsongwriter Romeo am 18. März 2006, dass das Album ein bisschen düsterer werden solle, aber die generelle Richtung immer noch beibehalten würde, und „das klassische Zeug einen Punkt erreichte, an dem wir die Musik ein bisschen weiterentwickeln mussten.“ Es sollte immer noch eine Menge klassischer Einflüsse geben, wenn auch nicht mehr so offensichtlich wie zum Beispiel bei Out of the Ashes auf The Divine Wings of Tragedy.
Die geplanten Erscheinungstermine, unter anderen Ende 2006, wurden mehrfach verschoben. Im August 2006 wurde ein Entwurf eines Covers im Internet durchgestochen, das darauf hindeutete, dass der Titel des Albums mit dem Song Paradise Lost identisch sein würde. Dieses zunächst nur als vorläufig bezeichnete Cover erwies sich später als offizielles Albumcover. Das vollständige Cover, samt Rückseite, wurde am 12. Mai 2007 veröffentlicht, als Symphony X auf ihrem Myspace-Profil und der Website des deutschen Plattenlabels SPV Serpent’s Kiss und Samples einiger Tracks des Albums als MP3 zum Download bereitstellten.
Neben der Standard-Jewelcase-Edition wurde das Album in weiteren Editionen veröffentlicht: eine Sonderedition mit Digipak-Verpackung, die eine DVD im 5.1-Mehrkanal-Ton und Musikvideos zu Serpent’s Kiss und Set the World on Fire enthält und eine limitierte Edition mit einer DVD mit Aufnahmen aus der Bandgeschichte, die erstmals ausschließlich in Geschäften der US-amerikanischen Ladenkette f.y.e. erhältlich war.[5] Bei Vorbestellung über Newbury Comics, einer US-amerikanischen Handelskette für Comics, erhielten die ersten 500 Exemplare ein signiertes CD-Booklet.
Thom Jurek bewertet das Album auf AllMusic mit 4/5 Sternen und nennt „Paradise Lost einen neuen Höhepunkt für dieses Quintett." "Die Songs hier haben eine direkte Anziehungskraft, die trotz ihres erstaunlichen kompositorischen Rahmens nichts auslässt.“ Er lobt das virtuose Spiel Musiker und den Gesang Allens: „… der in Sachen Ausdruckskraft und Power nur von Ronnie James Dio übertroffen wird ... und über das hinaus [geht], was wir normalerweise im Bereich des Prog-Metal sehen. Das Ironische daran ist, dass Paradise Lost gleichzeitig aggressiver, musikalisch nuancierter und konzeptionell ehrgeiziger ist.“ In der Publikumswertung erreicht es auf AllMusic 4,5/5 Sterne von 241 Nutzern.[1] Auf Prog Archives erringt es 3,8/5 Punkten, bei 546 Benutzern.[6]
Auf dem deutschsprachigen Progressive-Rock-Portal Babyblauen Seiten liegen die Bewertungen im positiven Bereich, dort erringt es 9,5/15 Punkte. Michael Büttgen gibt ihm 10/15 Punkte und schreibt: „Paradise Lost erreicht nicht ganz den Klassikerstatus von The Damnation Game oder The Divine Wings of Tragedy, gehört für mich aber auf jeden Fall zum besten, was ich in den letzten 10 Jahren von den Jungs gehört habe. Symphony X bleiben nach wie vor eigenständig, entwickeln sich weiter ohne alte Fans zu vergraulen oder bei anderen Bands klauen zu müssen.“ Andere Rezensenten bemängeln, dass das Album nach dem letzten Studioalbum vor immerhin 5 Jahren nur wenig neues zu bieten hat, und kritisieren die Geschäftspraxis, dass einige Zeit nach Erscheinen der CD, eine wenn auch hervorragend produzierte DVD in Dolby 5.1 nachgeschoben wurde. Gunnar Claußen hält es in einem rückblickenden Kommentar 2013 für ein bemerkenswertes Album, trotz einiger Mängel, wie sperrige und bis an die Grenze zur Unübersichtlichkeit stehender Songs.[7]
