Группа Paradise Lost была основана в 1988 в городе Халифакс в Великобритании.Названием Paradise Lost послужила одноименная поэма Джона Милтона. Группе потребовалось записать всего две демо-ленты, затем чтобы заключить контракт на полноценный альбом. В конце 1989 года группа Paradise Lost заперлась в ныне легендарной Academy Studios, результатом чего стал дебютный альбом Paradise Lost 1990 года, он отличался тяжелым звучанием, медленным темпом композиций, мрачной атмосферой, а также гроулингом вокалиста Ника Холмса. Он мгновенно стал стал самым продаваемым релизом Peaceville Records, а также группа Paradise Lost отправилась в европейское турне на разогреве дэт-метал-группы Autopsy. Очередной альбом Gothic 1991 года, записанный в том же стиле, звучал сильнее мелодично, отчасти благодаря появившимся партиям клавишных а также сопрано. Gothic принёс группе широкую известность. Вместе с этим альбомом группа попала на страницы всех музыкальных журналов а также последовали предложения от разных фирм грамзаписи. Оперативнее всех оказалась фирма Music For Nations, которая а также прибрала к рукам восходящих звёзд тяжёлой музыки. За ним последовал альбом Shades of God. Несколько мягче стал вокал Ника Холмса, же в музыкальном плане группа скорее двинулась в направлении классического дума согласно типу Candlemass а также Saint Vitus, лишь только вместе с сильнее экстремальным звучанием.

Последующий альбом группы Paradise Lost- Icon, вышел в 1993 году, - продолжил стилистические изменения, начатые в Shades of God. Композиции стали больше мелодичными, а также простыми по самой структуре, однако гроулинг Холмса сменился хриплым вокалом. Получившиеся манера отнюдь не вписывался в рамки дум/дэт метала а также был впоследствии назван Gothic metal. Еще затем выхода альбома группе доверили возглавлять известнейший голландский фестиваль Dynamo Open Air, на котором Paradise Lost выступили пред 100000 фэнов. В том же году на рынке появилось немедленно 2-ва видео группы, Music For Nations записали на видеоплёнку один из последних концертов группы, «добили» её клипами а также издали кассету почти под названием Harmony Breaks. Но Peaceville Records раскопали у себя в архивах запись концертного выступления 1989 года а также выпустили её почти под названием Live Death. Кстати, на официальном интернет портале эта кассета далеко не указана а также в настоящее время является раритетом. В 1994 году выходит мини-альбом Gothic EP, в какой вошли перезаписанные варианты двух песен вместе сParadise Lost а также ещё двух вместе с Gothic. Группа продолжала тем временем активную концертную деятельность. Помимо покорения традиционных метал-рынков вида Европы а также США, Paradise Lost удалось выступить в таких странах как Израиль а также ЮАР. Интенсивное турне оказало тяжёлое противодействие на барабанщика Мэттью Арчера, он оставил группу а также был заменён Ли Моррисом из хэви/пауэр-команды Marshal Law. Альбом 1995 года Draconian Times продолжил тенденцию изменения звучания, отличаясь больше сложными аранжировками а также полным исчезновением элементов дэт-метала. Однако альбом вывел группу в ряд самых известных английских тяжёлых групп.

В 1997 году вышел альбом One Second, какой охарактеризовался резкой сменой стиля пусть даже на фоне того, что сейчас ни один альбом группы далеко не похож на остальные. В их музыку круто хлынула волна электроники, однако Ник Холмс запел сравнительно чистым голосом. Несмотря на это, альбом принёс такие хиты, как будто «One Second», «Say Just Words», «Blood of Another». Концертная разновидность альбома (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) - в принципе никак не содержал гитарного звука, же состоял совсем из сэмплов, был насыщен разного рода электроникой.

В последующих альбомах произошло некоторое музыкальное возвращение к «истокам» а также металлическому звучанию.

Последний на данное время альбом группы In Requiem (2007) характеризуется тяжёлым звуком, сочетанием элементов дум-метала а также готик-метала, возвращением к сочетанию "чистого" вокала вместе с гроулингом. На настоящий момент Paradise Lostрассматриваются музыкальными критиками как будто одни из первооткрытелей стиля готического метала.