Adını birebir İngiliz yazar John Miltonun başyapıtından alan Paradise Lost (Kayıp Cennet) 1989 senesinde İngilterenin Yorkshire kentinde underground bir metal grubu olarak kuruldu. Underground camiasına girişleri ise çıkardıkları üç demo ve bir single (In Dub) sayılmazsa 1990 yılında çıkan ilk albümleri "Lost Paradise" ile oldu. Fanzinlerin kapaklarında mezarlık önünde umutsuzca poz veren beş hüzünlü genç olarak tanındılar.

1991 yılında ise Peaceville Records etiketiyle çıkan "Gothic" albümü geldi. Bu albümden önce metal müzikte "gothic metal" olarak tabir edilen bir kategori yoktu. Ama Paradise Lost bu albümüyle müziklerinin türünü belirledi ve gothic metal denilen yeni bir akım başlattı. "Gothic"le beraber grubun ilk profesyonel kariyer başarısı geldi ve ilk Avrupa turnelerine çıktılar.

1992 senesinde piyasaya çıkan "Shades of God" grubun üçüncü albümüydü ve öncesinde çıkan singledaki bugün bile dillerden düşmeyen efsane "As I Die" parçasını içeriyordu. Hemen ardından "Icon" geldi ve albüm modern Heavy Metal için bir mihenk taşı olarak kabul edildi. Müzik daha heyecan verici bir hal aldı, ama o karamsar hava, o depresif etmosfer devamını sürdürdü.

Sıradaki albüm "Draconian Times" (1995) oldu. "Icon"un karakter olarak ikiziydi ve grubun ekonomik açıdan en başarılı albümüydü. Ansızın, eşsiz müziklerini yaratana dek yıllarca bıkmadan usanmadan çalışan grup, müziksel anlamda bir kavşağa gelmiş bulundu. Grubun lideri Greg Mackintosh elektronik aletler ilgilenmeye başladı ve grubu neredeyse metal müziğin dışında apayrı bir yere sürükledi. Sonuç "One Second" (1997) oldu. Bu albüm grubun fan kitlesini adeta ikiye böldü. Müzik, grubun içine işleyen karamsar havayı yine veriyordu ama metal müzik bekleyen Paradise Lost hayranları için yetersizdi. Böylece orijinal Paradise Lost hayranları grupla beraber bu macerada ilerlemeye devam etti.

Metal camiasının beklentileri üzerine "Host" ve "Believe in Nothing" ile grup geçmiş müziklerine geri bir dönüş yaptı. Özellikle "Believe in Nothing" grup için ikinci büyük değişim sayıldı.

2002 senesinde çıkan "Symbol of Life" ise grup için yeni bir başlangıcın temsilcisiydi. Grup bu albümle geçmişlerine bir yolculuk yaptıklarını hayranlarına duyurdu. Eski parçalarını daha değişik bir tarzda yeniden coverladı.

Grubun bu albümden sonra 2003 senesinde Strange Fruit Records etiketiyle (Dracoain Timese dek olan parçalarının canlı kayıtlarını içeren) "At the BBC" isimli bir albümü, "Erased" adında bir singleı ve 2004 senesinde Bolt Throwerla çıkardıkları bir split cdsi (Demolishing England) bulunuyor. Paradise Lost karanlık, umutsuz, ve daha önce kimsenin yapmadığı kendilerine has müzikleriyle özellikle 90 gençliğinin sesi olmayı başardı.