Группа была основана в 1988 в городе Галифакс в Великобритании. Названием для группы послужила одноимённая поэма Джона Милтона. Группе потребовалось записать всего две демо-ленты, чтобы получить контракт на полноценный альбом. В конце 1989 года группа заперлась в ныне легендарной Academy Studios, результатом чего стал дебютный альбом Lost Paradise 1990 года, он отличался тяжёлым звучанием, медленным темпом композиций, мрачной атмосферой и гроулингом вокалиста Ника Холмса. Он мгновенно стал самым продаваемым релизом Peaceville Records, и группа отправилась в европейское турне на разогреве у дэт-метал-группы Autopsy. Следующий альбом Gothic 1991 года, записанный в том же стиле, звучал более мелодично, отчасти благодаря появившимся партиям клавишных и сопрано. Gothic принёс группе широкую известность. С этим альбомом группа попала на страницы всех музыкальных журналов и последовали предложения от различных фирм грамзаписи. Оперативнее всех оказалась компания Music For Nations, которая и прибрала к рукам восходящих звёзд тяжёлой музыки. За ним последовал альбом Shades of God (1992). Несколько мягче стал вокал Ника Холмса, а в музыкальном плане группа скорее двинулась в направлении классического дума по типу 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.
Группа продолжала активную концертную деятельность. Помимо покорения традиционных метал-рынков, т. е. Европы и США (в 1995 они были вне конкуренции и снискали как признание Metallica, заметивших их в 1992-м году, так и Pantera), Paradise Lost удалось выступить в таких странах как Израиль и ЮАР. Интенсивное турне оказало тяжёлое воздействие на барабанщика Мэттью Арчера, он оставил группу и был заменён Ли Моррисом из хэви/пауэр-команды Marshal Law. Альбом 1995 года Draconian Times продолжил тенденцию изменения звучания, отличаясь более сложными аранжировками и полным исчезновением элементов дэт-метала. Этот альбом вывел группу в ряд самых популярных английских тяжёлых групп. Одной из идей создания прославленного альбома было желание музыкантов поэкспериментировать с голосом Холмса, который в некоторых композициях с этого релиза манерой пения напоминает Джеймса Хетфилда.
В 1997 году вышел альбом One Second, который охарактеризовался резкой сменой стиля даже на фоне того, что ни один альбом группы не похож на остальные. Теперь звучание Paradise Lost можно было описать, как gothic rock с активным использованием клавишных и электронных эффектов.
По словам Грега, One Second называется так потому что он о том этапе,

Стилистические изменения гитарист объяснил тем, что с выходом Дракониан Таймс люди ожидали больше изменений в звучании группы, но по-факту это оказались изменения относительно Icon (1993). C Секундой парни захотели в полной мере самостоятельно и независимо от слушателей развивать свои идеи. Подробное интервью о тех годах на официальной странице музыкальной группы.
Ник Холмс запел чистым голосом. Многие хиты с альбома, особенно одноименная 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. Данная работа стилистически тяготеет к предыдущему релизу, но содержит меньше электроники и больше гитарного (альтрок- и гранжевого) саунда.
Альбом 2002 года Symbol of Life спродюсировал Rhys Fulber (Front Line Assembly, Fear Factory) и был выпущен на лейбле G.U.N., подразделении BMG. Звук на альбоме ещё более тяжёлый, чем на Believe In Nothing, однако едва ли имеет много общего с предыдущим и со старым материалом группы. На «Symbol Of Life» активно используются индустриальные электронные эффекты, жесткие современные nu-metal (Isolate) риффы и семплированные ударные. Одно лишь остается неизменным: фирменная меланхоличная атмосфера и тексты Холмса. Треки Erased и 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).
2011 год ознаменовался для группы и её фанатов переизданием альбома Draconian Times, приправленного выходом концертного DVD «Draconian Times MMXI» (2011). Положительная реакция публики на мини-тур в поддержку классического альбома группы по отзывам самих музыкантов «превзошла все наши ожидания», а также позволила Грегору Макинтошу вспомнить как и почему он играл в прежние времена так, а не иначе. Стоит добавить, что Драконовские Времена после переиздания звучат действительно чище: ремастеринг пошёл альбому на пользу, да и раннее неизданные песни порадуют любого ценителя PL.
В результате всего этого дела 23 апреля 2012 года состоялся релиз очередного полноформатного альбома группы — Tragic Idol, ставшего 13-м по счету для музыкального коллектива. Большинство музыкальных обзоров, рецензий и интервью с группой о новой работе свидетельствуют о том, что этот альбом — один из сильнейших за всю историю группы. Аарон Аеди уже назвал Tragic Idol «лучшим» и «любимым», а Грег Макинтош ощущает его как продолжение альбома Icon (1993) — настолько близок ему Tragic Idol по стилю и атмосфере. Кроме того, любой, кто знает творчество этих выходцев из Соединенного Королевства, согласится, что "Fear Of Impending Hell" поразительно похожа по структуре на "Hallowed Land" с упомянутого выше Draconian Times, а эпичная "The Glorious End" напоминает "Jaded", которой и завершаются Драконовские Времена. В целом - альбом получился более жестким и мелодичным, чем его предшественник. Клавишные семплы в теле песни присутствуют только в old school Doom Metal треке "Solitary One", с которой и стартует Трагический Идол, а элементов Doom'a в сочетании с классическим heavy metal'ом (послушать ту же "In This We Dwell") этот релиз несёт в себе много больше. Так, например, вторая композиция под названием "Crucify" написана под нескрываемым музыкантами влиянием на них дедов тяжелого рока (равно как и основоположников пред-дума) Black Sabbath.
В апреле 2012 года группа начала масштабный тур по UK при поддержке Insomnium а также впервые с 1995 года попала в Австралию где имела большой успех. По данным журнала Decibel, посвятившего Paradise Lost специальный выпуск номера, единственным, о чём сожалеет лидер и вокалист группы Ник Холмс, является то, что музыканты «не успели вовремя сориентироваться и подготовить аудиторию с тем, чтобы быть известными в Штатах». «Это позор. Ты не можешь всегда давать концерты многотысячным залам но зато, когда о тебе знают в стране — ты можешь сделать тур» — признался музыкант в интервью журналу Decibel Magazine за апрель-май 2012 года в Северной Америке. Несколько позже группа дала серию концертов в Штатах в рамках «Barge To Hell», а также выступила как специальный гость вместе с Katatonia и Devin Townsend Project в ходе турне «Epic Kings and Idols tour in the USA». Внимательный наблюдатель несомненно заметил ряд комментариев на You Tube и иностранных интернет-порталах о тяжелой музыке, оставленных людьми, присутствовавшими на тех концертах.
Смысл их сводится, в основном, к следующему: а) Paradise Lost по-прежнему группа едва и едва известная в Штатах (и, тем не менее, уже имеет свою аудиторию) б) Многие американцы говорят, что "этот вокалист разнёс бы в пух и прах Джеймса Хетфилда из Металлики, если бы они выступали на одной сцене. Но музыка впечатляет, это да" и т.п.
Так или иначе, сие подобие анализа творческой активности группы в США нельзя назвать в полной мере объективным, а потому, обратим внимание читателя на то, что живые выступления группы в 2012-2013 годах стали а) Жестче и агрессивнее (к примеру, As I Die на одном из метал-фестов звучит отменно по нынешним меркам, в сравнении с оригинальной композицией с альбома 1992-го года) б) Ник Холмс, в то же время, стал чаще терять свой голос, объясняя это недосыпом и усталостью. Кроме того известно, что частые перелеты из страны в страну ведут к "перестройке" систем человеческого организма (а вернее, скоростной и далеко не всегда качественно позитивной попытке его адаптации к изменяющимся условиям) на фоне частой смены часовых поясов и нарушения биоритмов индивидуума. Проще говоря, постоянный напряг ведёт к истощению, которое становится все труднее и труднее скомпенсировать при плотном ритме жизни (концертном графике).