Группа была создана в 1988-м году в городе Галифакс (Англия). В стартовый состав вошли вокалист Ник Холмс (Nick Holmes), гитарист Грегор Макинтош (Gregor Mackintosh), второй гитарист Аарон Аеди (Aaron Aedy), басист Стивен Эдмондсон (Stephen Edmondson) и барабанщик Мэтт Арчер (Matt Archer). В последующие годы группа почти не менялась.

Группе потребовалось записать всего две демо-ленты, чтобы получить контракт с компанией Peaceville, но на большее ан-дерграундной группе, исполняющей death metal, рассчитывать не приходилось. В конце 1989-го года группа заперлась в студии Academy. Результатом их работы стал альбом Lost Paradise, достаточно посредственно записанный, но революционный с музыкальной точки зрения. Это был первый в мире диск в стиле doom/death, с тяжелыми гитарами, чередованием крайне медленных пассажей и дэтовых фрагментов, утробным рыком вокалиста и невиданной доселе в металлической музыке концентрацией депрессивности. Сейчас как слушатели, так и музыканты относятся к альбому Lost Paradise несколько снисходительно, называя его первым блином и т.д., но в 1990-м году так не играл никто, и диск просто не могли не заметить. Он мгновенно стал самым продаваемым релизом Peaceville, и группа отправилась в европейское турне. Второй альбом Gothic записывался в той же студии и с тем же продюсером, но звучал гораздо более солидно, а его музыка привела в восторг как поклонников, так и журналистов. В песнях PARADISE LOST проявилась неслыханная в экстремальной музыке мелодичность, в основном передаваемая гитарой Грега Макинтоша, основного композитора группы. Не подкачал и Ник Холмс, выдав целый набор достаточно интеллектуальных и непростых для понимания текстов. Кроме того, группа первой не побоялась поддержать изобретение швейцарцев CELTIC FROST и вставила в песни партии клавишных и женского сопрано. Сейчас в этом нет ничего необычного, а тогда это было невероятное новаторство.

Второй альбом Gothic произвел фурор в Европе, что привело к активизации других фирм грамзаписи. Оперативнее всех оказалась компания Music For Nations, которая и прибрала к рукам восходящих звезд. Дебют PARADISE LOST на новой фирме обозначил новую линию. На Shades Of God отчетливо виден переход к более прямолинейному звучанию. Несколько мягче стал вокал Ника Холмса, а в музыкальном плане группа двинулась скорее в направлении классического doom metal по типу CANDLEMASS и ST. VITUS. В записи принимал участие клавишник из легендарной британской прог-рок группы ENID Роберт Джон Годфри (Robert John Godfrey).

PARADISE LOST нашли нужное направление развития, и диск 1993-го года Icon продемонстрировал движение в сторону более простых по структуре композиций с уклоном на мелодичные гитарные партии и запоминающиеся припевы. Ник Холмс полностью отказался от рычания и стал петь в духе Джеймса Хэтфилда (METALLICA), что для новых песен подходило гораздо больше. В результате получился чуть ли не лучший диск парадайзов, до отказа забитый умопомрачительными хитами и великолепными мелодиями. Уже после выхода Icon группу стали обвинять в коммерциализации, однако группа уверенно набирала обороты, привлекая под свои знамена все больше и больше поклонников. В 1994-м году лейбл выпустил мини-альбом Gothic ЕР, в который вошли перезаписанные варианты двух песен с Lost Paradise и еще двух с Gothic. PARADISE LOST были крайне недовольны этим релизом, но ничего не могли поделать. Группа тем временем продолжала активную концертную деятельность. Помимо покорения традиционных метал-рынков типа Европы и США, PARADISE LOST умудрились выступить в таких экзотических странах, как Израиль, ЮАР и Эстония.

Интенсивные турне вымотали Мэттью Арчера, который, к тому же, не совсем был доволен новым музыкальным курсом группы. Он оставил состав и был заменен Ли Моррисом (Lee Morris, ex-MARSHAL LAW, LIFE). Когда он присоединился к PARADISE LOST, у Грега и Ника был практически готов материал для нового диска, который получил название Draconian Times. Диск вышел в 1995-м году и представлял собой логическое продолжение Icon, только с еще большим количеством нюансов, более продуманными аранжировками и окончательным отказом от элементов дэта. Ни один человек, начавший знакомство с парадайзами с альбома Draconian Times не подумал бы, что эта группа всего каких-то лет пять назад играла брутальный дэт.

Слушали PARADISE LOST теперь совсем другие люди, отнюдь не поклонники дэта и трэ-ша, как в начале карьеры. После Draconian Times на группу обратили внимание, как готы, так и любители хард-рока. Фанаты PARADISE LOST обнаружились даже в журнале Classic Rock, который обычно не пишет о группах тяжелее IRON MAIDEN. А готов порадовало исполнение парадайзами кавер-версии классической песни гот-легенды SISTERS OF MERCY Walk Away. Draconian Times вывел PARADISE LOST в ряды самых популярных английских тяжелых групп. Многие ожидали, что группа будет продолжать в том же духе, но сами музыканты решили иначе. Свой новый диск One Second они сделали совершенно не похожим на все предыдущие работы. Это даже не готик-метал, это скорее го-тик-рок с основной мелодической нагрузкой на клавишные инструменты. На альбоме, правда, еще осталось достаточное количество гитар, но тот факт, что Грег написал все песни на клавишных, нельзя не заметить. Многие отвернулись от PARADISE LOST после такого диска, но сами музыканты ничуть не расстраивались по этому поводу. Грег и Ник говорили во всех интервью, что именно такую музыку они предпочитают в настоящий момент, а поскольку на земле нет групп, песни которых нравятся нам на сто процентов, нам приходится писать их самим. Впрочем, хороших песен на One Second и вправду хватало. Вслед за альбомом последовало глобальное турне, в ходе которого музыканты заглянули и в Россию. 6 марта 1998-го года они отыграли в Москве единственный концерт, который был фантастически принят публикой. Контракт с Music For Nations закончился в 1998-м году, и группу взяла под свою опеку транснациональная корпорация EMI. На прощанье Music For Nations решили издать сборник лучших вещей Reflection, добитый тремя концертными вещами. Эти три композиции были взяты с видеокассеты One Second Live In London, которую выпустил английский фэн-клуб группы.

Альбом Host вышел в 1999-м году и напрочь разочаровал практически всех поклонников творчества PARADISE LOST. К тяжелому року он практически не имеет никакого отношения, скорее просятся параллели с творчеством других английских адептов депрессии - DEPECHE MODE. Гитары и барабаны окончательно отошли в тень, уступив место сэмплерам и синтезаторам, так что большинство услышавших диск искренне недоумевают, зачем группе два гитариста. Любители готики встретили диск прохладно, отметив, что ни одного серьезного хита Host не содержит. Host создавался под влиянием целого ряда проблем в семьях музыкантов. Проблемы продолжились, как только началось турне. После концерта в ирландском городе Корк Грегор принял на грудь чрезмерно большое количество алкогольных напитков и при загрузке в автобус не устоял на ногах. Результат - перелом руки, которая потом еще и неправильно срослась, так что у врачей возникли сомнения, сможет ли Грегор вообще играть на гитаре. В течение следующих нескольких месяцев турне он в основном стоял за клавишами, а на гитаре играл барабанный техник Энди Корне (Andy Corns). В итоге все обошлось, но понервничать группе пришлось. После выхода Host большинство металлистов поставили на PARADISE LOST большой и жирный крест. Поэтому сообщения о том, что группа на следующем диске планирует вернуться к более тяжелому звучанию, воспринимались с большим недоверием. Тем не менее, музыканты свое обещание сдержали, и альбом Believe In Northing снова звучит тяжело и агрессивно, хотя электроника по-прежнему присутствует.

Очередной альбом Symbol Of Life вновь стал хитом в континентальной Европе. В марте 2004-го года группу оставил ударник Моррис, и на его место взяли Джеффа Сингера (Jeff Singer, ex-BLAZE, KILL II THIS).
В 2005-м состав выступил в Москве.