Група "Paradise Lost", яка взяла свою назву з епічної поеми Джона Мільтона, стартувала в 1988 році в містечку Халіфакс (графство Йоркшир). В оригінальний склад увійшли Нік Холмс (р. 7 січня 1970; вокал), Грег Макінтош (р. 20 червня 1970; гітара), Аарон Аеді (р. 19 грудня 1969; гітара), Стів Едмондсон (р. 30 грудня 1969;
бас) і Меттью Арчер (р. 14 липня 1970; ударні). В кінці 80-х квінтет записав пару демок, "Drown in Darkness" і "Frozen Illusion", за допомогою яких причалив до гавані під назвою "Peaceville Records". У 1990 році вийшов диск "Lost Paradise", що став, по суті, першим релізом в стилі дум-дез. Спочатку мало хто зацікавився творчістю йоркширських музикантів, але коли вийшов другий альбом, в пресі замигтіли захоплені рецензії.
Назва "Gothic" досить добре характеризувало депресивну музику "Paradise Lost", в якій з'явилися жіночі вокали і клавішні. На підтримку диска команда провела своє перше європейське турне і тим самим привернула в свій стан чимало шанувальників, а також зацікавила лейбл "Music for Nations", з яким було укладено новий контракт.
На двох наступних роботах група поступово стала позбавлятися від детового присмаку, зберігаючи при цьому фірмову депресивну меланхолійність. Найбільш значним твором того періоду стала пісня "As I Die", особливо полюбився шанувальникам "Lost" і що стала на довгий час концертним фаворитом. Зміна курсу, а також виснажливі гастролі привели до відходу Меттью Арчера, який поступився ударну установку Лі Морісу. У 1995 році група остаточно вивела формулу "готичного металу" з роботою "Draconian Times". Альбом зайняв 16-е місце в чартах і став найбільш комерційно успішним релізом "PL" на той момент.
Яке ж було здивування "парадайзофілов", коли два роки тому на світ з'явився нашпигований електронікою "One Second". У результаті деякі з фанів відвернулися від "Paradise Lost", але більшість зберегло вірність. Крім того, серед шанувальників команди з'явилося багато неофітів, що дало музикантам привід ще поекспериментувати з мейнстримом.
Виявилося, що група здатна видавати якісний матеріал і без важких гітарних рифів, але, вдосталь награвшись з новомодними фішками, колектив все ж повернувся до свого коріння. У 2002 році команда під керівництвом продюсера Ріса Фулбера ("Fear Factory", "Front Line Assembly") видала потужний альбом "Symbol Of Life". Крім власного матеріалу "Paradise Lost", за який як завжди відповідали Холмс і Макінтош, диск містив пару каверів: "Small Town Boy" від "Bronski Beat" і "Xavier" від "Dead Can Dance". У 2004-му десятирічна стабільність складу була порушена відходом Морріса, чиє місце зайняв Джесс Сінгер.
У тому ж році все з тим же Фулбером був записаний "ювілейний" десятий студійник, сесії якого проходили в Лінкольнширі і Лос-Анджелесі. Озаглавлений просто "Paradise Lost" і повертав слухача до важкого гітарного саунду, альбом довів що у музикантів ще досить пороху в порохівницях.