Группа была основана в 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. Альбом стилистически тяготеет к предыдущему, но содержит меньше электроники и вновь насыщен гитарным звуком.
Альбом 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).
23 апреля 2012 года состоялся релиз очередного полноформатного альбома группы — Tragic Idol. Большинство музыкальных обзоров, рецензий и интервью с группой об этой работе свидетельствуют о том, что этот альбом — один из сильнейших за всю историю группы. Аарон Аеди уже назвал Tragic Idol «лучшим» и «любимым», а Грег Макинтош ощущает его как продолжение альбома Icon (1993) — настолько близок ему Tragic Idol по стилю и атмосфере. В апреле 2012 года группа начала масштабный тур по UK при поддержке Insomnium а так же впервые с 1995 года попала в Австралию где имела большой успех. По данным журнала Decibel, посвятившего Paradise Lost специальный выпуск номера, единственным, о чём сожалеет лидер и вокалист группы Ник Холмс, является то, что музыканты «не успели вовремя сориентироваться и подготовить аудиторию с тем, чтобы быть известными в Штатах». «Это позор. Ты не можешь всегда давать концерты многотысячным залам но зато, когда о тебе знают в стране — ты можешь сделать тур» — признался музыкант в интервью журналу Decibel Magazine за апрель-май 2012 года в Северной Америке.
В июне 2012 года музыканты опубликовали сборник "Lost In Time" для online-прослушивания или свободного скачивания.
