Группа была основана в 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, дополненный тремя концертными вещами. В паузах между турне Ник Холмс принял участие в записи сольного альбома певицы Лив Кристин 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. Альбом стилистически тяготеет к предыдущему, но содержит меньше электр