Paradise Lost се събират през 1987-ма година в Халифакс, Англия, когато Nick Holmes и Gregory Mackintosh се запознават на местен концерт. Оригиналният състав е запазен и до днес с изключение на барабанистите (Matthew Archer свири в групата до “Icon”, а Lee Morris до март 2004-та). След записването на две демота, Paradise Lost подписват с Peaceville Records и през 89-та година издават дебютния си албум "Lost Paradise". Това е един рядко срещан дет метъл албум. През март 1991 година се появява вторият им албум, озаглавен "Gothic". Представя готическа атмосфера (явява се и кръщение на целия стил готик метъл) и мелодични препратки, включващи женските вокали на Sarah Marrion. Дори и днес, 14 години по-късно, влиянието на Paradise Lost е ясно различимо при групи като HIM и The Rasmus. За третата си творба Paradise Lost се обръщат към по-голям лейбъл - Music For Nations. След издаването на "Shades Of God" през 1992-ра година, четиримата музиканти заминават за първото си голямо европейско турне. С петия си албум "Draconian Times" (издаден през 95-та година) бандата се завръща към корените си на мейнстрийм рок формация. Излизането му е причина Paradise Lost да заминат на голямо турне включващо почти всички големи епропейски и азиатски държави. Достигат дори до Австралия. До днес "Draconian Times" е продаден в повече от един милион копия по целия свят. През 96-та година музикантите си взимат заслужена почивка, но още през следващата 97-ма влизат в студио за записите на шестия си дългосвирещ албум - "One Second". За старите фенове това е моментът, в който групата променя стила си и го ориентира към по-леко и лесно възприемчиво звучене. Това обаче не пречи на Paradise Lost да спечелят още много нови почитатели. 98-ма е годината за поредна смяна на лейбъла. Подписан е договор с EMI Records. През 1999-та албумът им "Host" е издаден от този лейбъл, а текстовете и настроенията в него отразяват емоционалното състояние на Nick, чийто баща умира от рак в началото на същата година. Това е и най-голямата промяна в стила на Paradise Lost, защото използването на електронни елементи замества досегашното тежко метъл звучене. За "Believe in Nothing" (2001) групата наема продуцента John Fryer (Nine Inch Nails, HIM). Това е албумът, в който се слага край на прахосването на времето им с използването на поп ориентирани мелодии. С издаването на "Symbol of Life" (2002) Paradise Lost се връщат към корените си. Заедно с продуцента Rhys Fulber (Fear Factory, Front Line Assembly) вокалистът Nick Holmes, китаристите Gregor Mackintosh и Aaron Aedy, басистът Steve Edmondson и барабанистът Lee Morris успяват да дадат на този запис част от силата на старите творби, но и да запазят и изграденото с по-новите им албуми звучене. Paradise Lost демонстрират вдъхновенията, които получват и от колегите си, включвайки в албума кавър на песента "Xavier" на Dead Can Dance. Правят поредната смяна на барабаниста си и засега титуляр за тях е Jeff Singer (ex- Blaze). Най-новият, десети албум на Paradise Lost, е едноименен. Той затваря един своеобразен цикъл, показвайки известно завръщане към някои от старите най-тежки инструментали. "Paradise Lost" е записан между януари и юни 2004 година в Chapel Studios, Лос Анджелис. За бек вокалите във "Forever After" и "Over the Madness" помагат Heather Thompson и Leah Randi
