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

Следующий альбом, "Gothic" 1991 года, записанный в том же стиле, звучал более мелодично, отчасти благодаря появившимся партиям клавишных и сопрано. Хотя стилистически "Gothic" это по-прежнему дум-дэт (только более разнообразный и передовой для своего времени за счет женского вокала, чередующегося с гроулингом мистера Холмса в паре песен) именно с выходом этого альбома музыкальные критики связывают начало стилю Gothic Metal. Paradise Lost это та группа, которая никогда не боялась генерировать свои идеи, развиваясь в духе своего времени и даже несколько опережая его. Дальше речь пойдет о некоторых весьма интересных стилистических девиациях в звучании коллектива, но сперва интересный факт, мало кому широко известный.

Цитата (Андерс Нюстрём):

Существуют два альбома Paradise Lost, которые значат для меня и Katatonia больше, чем остальные. Первый, это, конечно, мастерский и определивший направление жанра "Gothic"; так или иначе, второй оказался чем-то вроде "черной лошадки" в дискографии Paradise Lost. Я согласен с теми, кто говорит, что песни на этом альбоме "слишком электронные" и "недостаточно тяжелые", но, в отличие от таких людей, я был достаточно открыт, чтобы понять - этот альбом хорош. "Host" включает в себя ряд песен, которые легко можно назвать лучшими в их дискографии!

Действительно, второй полноформатный альбом принёс группе широкую известность. С этим альбомом группа попала на страницы всех музыкальных журналов и последовали предложения от различных фирм грамзаписи. Оперативнее всех оказалась компания 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", дополненный тремя концертными вещами. В паузах между турне Ник Холмс принял участие в записи сольного альбома певицы Лив Кристин 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. Альбом стилистически тяготеет к предыдущему, но содержит меньше электроники и вновь насыщен гитарным звуком. Впрочем, "Believe In Nothing" объективно является одним из самых спорных (читай "сделанных через силу") альбомов. 

Цитата (Грегор Макинтош):

В "Believe In Nothing", безусловно, тоже было несколько хороших песен, но они были неправильно преподнесены публике. Запись местами просто не удалась. Тогда нам пришлось пойти на слишком большое количество компромиссов, что, к сожалению, отрицательно сказалось на качестве музыки и оставило тяжелый осадок на душе. Именно по этой причине, работая над "Symbol Of Life", мы не упускали ни малейшей детали. Если какая-нибудь песня не устраивала всех нас на сто процентов, она сразу же забраковывалась.

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

23 апреля 2012 года состоялся релиз очередного полноформатного альбома группы, озаглавленного "Tragic Idol". Большинство музыкальных обзоров, рецензий и интервью с группой об этой работе свидетельствуют о том, что этот альбом - один из сильнейших за всю историю группы. Аарон Аеди уже назвал "Tragic Idol" "лучшим" и "любимым", а Грег Макинтош ощущает его как продолжение альбома "Icon" (1993) - настолько близок ему "Tragic Idol" по стилю и атмосфере.

В апреле 2012 года группа начала масштабный тур по Великобритании при поддержке Insomnium, а также впервые с 1995 года попала в Австралию, где имела большой успех. По данным журнала Decibel, посвятившего Paradise Lost специальный выпуск номера, единственным, о чём сожалеет лидер и вокалист группы Ник Холмс, является то, что музыканты "не успели вовремя сориентироваться и подготовить аудиторию с тем, чтобы быть известными в Штатах".

26 марта 2013 года Ник Холмс в своем Твиттере сообщил, что в этот день группе исполняется 25 лет! Параллельно этой новости появилась и другая: вокалист прославленной команды зарегистрировался на "джастгивинге" для того, чтобы собрать 1000 фунтов стерлингов (по факту сумма сборов быстро перевалила за тысячу) и сделать пожертвование в пользу детей с глубокими умственными, эмоциональными и психологическими ограничениями. Собранные пожертвования исполнитель пообещал передать в организацию, занимающейся арт- и музыкальной терапией с такими детьми. К сожалению, жители России не имели технической возможности помочь вокалисту, но зато помочь певцу смогли зарубежные фанаты коллектива и даже Адриан Эрландссон.

Решивший принять участие в благотворительном велокроссе исполнитель сообщил, что Century Media издаст масштабную компиляцию самых заметных альбомов лейбла последнего времени. В рамках этого сборника будет переиздан альбом Paradise Lost 2007-го года, получивший название "In Requiem". Таким образом Century Media делает подарок группе и её фэнам, дабы они могли отпраздновать четверть века существования коллектива.

Кроме того, в августе месяце на официальном сайте Paradise Lost Аарон Аэди заявил, что группа в скором времени издаст компиляцию редких песен. Известно, что сборник включает в себя бонусы и би-сайды, изданные в период с 2007-го по 2012-й годы. Наиболее сладкой новостью является тот факт, что грядущий релиз под названием "Tragic Illusion 25" вместит в себя одну совершенно новую песню под названием "Loneliness Remains" и перезаписанные в студии нетленки "Gothic" и "Our Saviour" - известные песни с первых двух альбомов группы.

Отличительной чертой концертных дат этого периода является тот факт, что Холмс вернулся к гроулингу, исполняя живьем треки типа "Gothic" и "Rotting Misery". Кроме того, Сentury Media издала компакт-диск с записью юбилейного шоу, состоявшегося 3 ноября 2013 в Лондоне.

В сентябре 2014 года музыканты отыграли большой сет в Римском античном театре. Выступление, состоявшееся в Пловдиве (Болгария), было заснято на видео для последующего выпуска на Blue Ray в 2015 году. Этот концерт был первым в истории коллектива, на котором группа исполнила 7 треков при поддержке филармонического оркестра и хора.

В конце осени 2014 года группа отправилась в студию для записи нового альбома, имеющего отчетливую дэт-метал грань и сюрпризы, характерные для фанатов первых альбомов Paradise Lost. 1 июня 2015 года выходит альбом "The Plague Within".

1 сентября на лейбле Nuclear Blast вышел 15-ый альбом группы - "Medusa". Релиз в своей стандартной версии состоит из восьми композиций. Вот как охарактеризовал звучание Медузы Ник Холмс: «Мне кажется, по настроению и звуку этот релиз ближе всего нашему третьему альбому, Shades Of God. Но, в сравнении, он более сложный, лучше сыгранный и лучше спродюсированный. Однако с точки зрения стилистики это нечто среднее между Gothic и Shades Of God — с небольшим современным налетом».