Группа была основана в 1988 в городе Галифакс в Великобритании. Названием для группы послужила одноименная поэма Джона Милтона. Группе потребовалось записать всего две демо-ленты, чтобы получить контракт на полноценный альбом. В конце 1989 года группа заперлась в ныне легендарной Academy Studios, результатом чего стал дебютный альбом "Lost Paradise" 1990 года, он отличался тяжелым звучанием, медленным темпом композиций, мрачной атмосферой и гроулингом вокалиста Ника Холмса. Он мгновенно стал стал самым продаваемым релизом Peaceville Records, и группа отправилось в европейское турне на разогреве у дэт-метал-группы Autopsy.

Следующий альбом, "Gothic" 1991 года, записанный в том же стиле, звучал более мелодично, отчасти благодаря появившимся партиям клавишных и сопрано. "Gothic" принёс группе широкую известность. С этим альбомом группа попала на страницы всех музыкальных журналов и последовали предложения от различных фирм грамзаписи. Оперативнее всех оказалась компания Music For Nations, которая и прибрала к рукам восходящих звёзд тяжёлой музыки. За ним последовал альбом "Shades of God". Несколько мягче стал вокал Ника Холмса, а в музыкальном плане группа скорее двинулась в направлении классического дума по типу Candlemass и Saint Vitus, только с более экстремальным звучанием.

Следующий альбом, "Icon", вышедший в 1993 году, продолжил стилистические изменения, начатые в "Shades of God". Композиции стали более мелодичными и простыми по структуре, а гроулинг Холмса сменился хриплым вокалом. Получившийся стиль не вписывался в рамки дум/дэт метала и был впоследствии назван Gothic metal. Уже после выхода альбома группе доверили возглавлять известнейший голландский фестиваль Dynamo Open Air, на котором Paradise Lost выступили перед 100000 фэнов. В том же году на рынке появилось сразу два видео группы, Music For Nations записали на видеоплёнку один из последних концертов группы, "добили" её клипами и издали кассету под названием Harmony Breaks. А Peaceville Records раскопали у себя в архивах запись концертного выступления 1989 года и выпустили её под названием "Live Death". Кстати, на официальном сайте эта кассета не указана и в настоящее время является раритетом.

В 1994 году выходит мини-альбом "Gothic" EP, в который вошли перезаписанные варианты двух песен с "Lost Paradise" и ещё двух с "Gothic". Группа продолжала тем временем активную концертную деятельность. Помимо покорения традиционных метал-рынков типа Европы и США, Paradise Lost удалось выступить в таких странах, как Израиль и ЮАР. Интенсивное турне оказало тяжёлое воздействие на барабанщика Мэттью Арчера, он оставил группу и был заменён Ли Моррисом из хэви/пауэр-команды Marshal Law. Альбом 1995 года, "Draconian Times", продолжил тенденцию изменения звучания, отличаясь более сложными аранжировками и полным исчезновением элементов дэт-метала. Этот альбом вывел группу в ряд самых популярных английских тяжёлых групп.

В 1997 году вышел альбом "One Second", который охарактеризовался резкой сменой стиля даже на фоне того, что ни один альбом группы не похож на остальные. Теперь звучание Paradise Lost можно было описать, как gothic rock с активным использованием клавишных и электронных эффектов. Вокал окончательно утратил "хриплоту", Ник Холмс запел чистым голосом. Многие хиты с альбома, особенно одноименная "One Second", а также "Say Just Words" и "Mercy" до сих пор исполняются на концертах. Произошли изменения и во внешнем виде группы - музыканты все, как один, сменили пышные хаеры на короткие прически. Концертная версия альбома (One Second Live) была издана на видеокассетах и впоследствии переиздана на DVD. Вслед за альбомом последовало глобальное турне, в ходе которого музыканты заглянули и в Россию. 6 марта 1998 они отыграли свой концерт в Москве.

Договор с Music For Nations закончился в 1998 году и группу к себе подписала одна из крупнейших фирм звукозаписи — EMI. "На прощанье" Music For Nations решили выпустить сборник лучших вещей — "Reflection", дополненный тремя концертными вещами. Скопировано с Dark-World.ru. В паузах между турне Ник Холмс принял участие в записи сольного альбома певицы Лив Кристин Deus Ex Machina. Он записал часть вокальных партий к песне "3 А. М.". Тем временем французская фирма Holy Records подготовила трибьют "Paradise Lost As We Die For…".

Следующий альбом, "Host" (1999), пошёл ещё дальше, гитарный звук почти полностью уступил место электронным семплам и клавишным, впрочем свою фирменную меланхоличную атмосферу группа не растеряла. Такие хиты, как "Nothing Sacred", "Behind The Grey", "So Much Is Lost", "Made The Same" вполне достойны звания одних из лучших песен, написанных Paradise Lost. "Host", как и последующий "Believe In Nothing" (2001), вышел на лейбле-мэйджоре EMI.

Стоит отметить, что эксперименты группы, начиная с альбома One Second, прошлись по вкусу далеко не всем поклонникам, именно с того момента берут начало знаменитые разговоры и споры об "опопсении" Paradise Lost - за альбом "Host" группу за глаза обзывали новым Depeche Mode. Парадокс, но продажи казалось бы более доступных для массовой публики "Host" и "Believe In Nothing" были заметно меньше, чем бестселлера "Draconian Times". "Believe In Nothing" стал вторым и последним альбомом Paradise Lost на лейбле EMI. Альбом стилистически тяготеет к предыдущему, но содержит меньше электроники и вновь насыщен гитарным звуком.

Альбом 2002 года "Symbol of Life" спродюсировал Rhys Fulber (Front Line Assembly, Fear Factory) и был выпущен на лейбле G.U.N., подразделении BMG. Звук на альбоме ещё более тяжелый, чем на "Believe In Nothing", однако едва ли имеет много общего с предыдущим и со старым материалом группы. На "Symbol Of Life" активно используются индустриальные электронные эффекты, жесткие современные гитарные риффы и семплированные ударные. Одно лишь остается неизменным: фирменная меланхоличная атмосфера и тексты Холмса. Треки "Erased", "Isolate" и "No Celebration" часто присутствуют и в современных концертных сет-листах группы.

Одноименный альбом "Paradise Lost" (2005) ознаменовал собой частичный возврат к "корням", стилистически его можно описать, как некий компромиссный сплав старого творчества ("Draconian Times") и более поздних релизов. Гитарный звук снова стал превалирующим в музыке группы, электроника практически ушла в небытие. Холмс и Макинтош снова обзавелись длинными волосами, словно намекая о том, что возврат к старому состоялся всерьез и надолго.

Альбом "In Requiem" (2007) характеризуется ещё более очевидным возвращением к саунду периода "Icon", "Draconian Times", только в более современном варианте и при некотором сохранении наработок периода 1997-2002 гг. Заодно "In Requiem" стал самым продаваемым со времен "Draconian Times".

В августе 2008 года ударник Джеф Сингер объявил о своём решении покинуть группу в связи с тем, что музыкальная карьера стала для него обременительной и не позволяет уделять время общению с семьёй. Некоторое время спустя новым ударником коллектива стал Адриан Эрландссон (Cradle Of Filth, The Haunted).

В сентябре-октябре 2009 года группа выпустила двенадцатый по счёту студийный альбом, который получил название "Faith Divides Us - Death Unites Us". Гитаристы Грег Макинтош и Арон Аэди впервые взяли в руки семиструнные гитары, а продюсером диска выступил Йенс Богрен. Звучание Paradise Lost стало ещё тяжелее, нежели на альбоме "In Requiem" - по крайней мере, сами музыканты признаются, что не писали столь агрессивных песен уже долгое время. Gothic Metal по-прежнему является главной и неотъемлемой составляющей стиля группы, но на "Faith Divides Us - Death Unites Us" в отдельных песнях отчётливо заметны элементы Doom Metal'а и даже классического Heavy Metal'а.

В начале 2010 года Paradise Lost вынуждены были временно сменить главного гитариста в связи с семейными проблемами Грега Макинтоша, который не смог продолжить концертный тур в поддержку нового альбома. Временным гитаристом коллектива стал Милли Эванс (по совместительству клавишник в группе Terrorvision).

7 ноября 2011 года через лейбл Century Media Records выходит DVD "Draconian Times MMXI". Группа отыграла свой самый сильный альбом 1996 года в рамках семи больших концертов, что проходили в следующих городах Европы: в Тилбурге, Бочуме, Лондоне, Париже, Афинах и в Тессалоники. Релиз включил в себя запись лондонского шоу в The Forum, которое состоялось 1 апреля, документальное видео, которое было снято бас-гитаристом Стивом Эдмондсоном во время тура, интервью продюсера Саймона Эферми, Ника Холмса, Грега Макинтоша, Аарона Аэди, Стива Эдмондсона и менеджера группы с 1990 года, Энди Фэрроу, в котором рассказывается история создания "Draconian Times", а также два промо-видео с последнего полноформатника "Faith Divides Us – Death Unites Us".

Вокал: Nick Holmes
Гитара: Gregor Mackintosh
Бас-гитара: Stephen Edmonson
Гитара: Aaron Aedy
Ударные: Adrian Erlandsson

Ударные:
(1988-1993) Matthew "Tudds" Archer
Ударные:
(1994-2004) Lee Morris
Ударные:
(2004-2008, на концертах в 2009) Jeff Singer
Ударные:
(на концертах в 2008) Mark Heron
Ударные:
(сессионно в 2009) Peter Damin
Гитара, клавишные, бек-вокал:
(на концертах, 2009-2011) Milly Evans

(2012) Tragic Idol
(2011) Draconian Times MMXI (Live)
(2009) Faith Divides Us-Death Unites Us
(2009) Drown in Darkness - The Early Demos (Compilation)
(2008) The Anatomy of Melancholy (Live)
(2007) In Requiem (Limited Edition Digipak)
(2007) In Requiem
(2005) Forever After (Single)
(2005) Paradise Lost
(2002) Symbol of Life
(2001) Mouth (Single)
(2001) Fader (Single)
(2001) Believe in Nothing
(1999) So Much Is Lost (Single)
(1999) Permanent Solution (Single)
(1999) Host
(1998) Reflection (The best of/Compilation)
(1997) Say Just Words (Single)
(1997) One Second (Single)
(1997) One Second
(1997) True Belief '97 (Single)
(1996) Live Enchantment
(1995) The Last Time (Single)
(1995) Draconian Times (Bonus CD)
(1995) Forever Failure (Single)
(1995) Draconian Times
(1994) Seals The Sense (EP)
(1994) Gothic (EP)
(1993) Icon
(1992) As I Die (Single)
(1992) Shades Of God
(1991) Gothic
(1990) In Dub (Single)
(1990) Lost Paradise
(1989) Live at Liverpool Polytechnic (18.03.89)
(1989) Frozen Illusions (Demo)
(1988) Paradise Lost (Demo)