Paradise Lost został założony przez Nicka Holmesa, Grega Mackintosha, Stevena Edmondsona, Aarona Aedy’ego oraz Matta Archera. Nazwa grupy jest inspirowana poematem Johna Miltona „Raj utracony”. Rozpoczęli karierę, wiążąc się z wytwórnią Music for Nations, w której stajni znajdowały się dwie inne grupy: Anathema i My Dying Bride. Albumy wydane przez te trzy grupy zostały określone mianem brytyjskiej szkoły doom-death metalu. Każda z nich grała muzykę wolną, ciężką do mrocznych, „gotyckich” tekstów. Za przełomową płytę Paradise Lost uznano album Gothic. Został on uznany za kanon gatunku, który nazwano gothic metal. Podobnie zresztą jak pozostałe dwie grupy, Paradise Lost nie przywiązał się do stylu muzycznego z pierwszych płyt. Stopniowo zaczęli rezygnować z charakterystycznych dla nich wokali (męski growl połączony z żeńskim wokalem), jednocześnie muzycznie zmierzając w kierunku bardziej klasycznych odmian metalu, niż samego death metalu. Kulminacją tego etapu muzycznego była płyta, która do dziś jest największym sukcesem komercyjnym Paradise Lost Draconian Times.
Przed nagraniem Draconian Times perkusistę Matta Archera zastąpił Lee Morris. Po nagraniu tego albumu kompozytor grupy, Greg Mackintosh zafascynował się instrumentami elektronicznymi. To, oraz inspiracje Sisters of Mercy, które zaczęły się manifestować przy okazji Draconian Times (cover utworu Walk Away na stronie B singla The Last Time), przyczyniły się do powstania zaskakująco lekkiej i prostej gitarowo płyty One Second, której bliżej było do rocka gotyckiego niż do metalu. Co więcej, dalej postępowała metamorfoza wokalna Nicka Holmesa, który na tej płycie śpiewał już czystym, popowym wręcz głosem, przy wsparciu śpiewającego perkusisty Lee Morrisa. Płyta była szokiem dla wielu fanów, oraz znakiem, że czas grupy na scenie metalowej się kończy. Wraz z tą płytą zakończył się także kontrakt grupy z Music for Nations, a grupa ruszyła na podbój świata, podpisując umowę z EMI. Rezultatem tej umowy były dwie kolejne płyty. Pierwsza z nich, Host jest już płytą niemal zupełnie elektroniczną. W brzmieniu zespołu nie ma nawet śladu grupy, która nagrywała pierwsze płyty. Przez wielu była porównywana do dokonań Depeche Mode (w szczególności do najbardziej gitarowej płyty Songs of Faith and Devotion oraz do Ultra), tym bardziej że jej producentem był Steve Lyon, który współpracował również z Depeche Mode.
Następna płyta była jednak sygnałem, że ten etap rozwoju grupa ma już również za sobą. Płyta Believe in Nothing stanowiła dziwny mariaż nowego brzmienia z rockiem. Od tego momentu grupa określa swoją muzykę jako dark rock. Płyta ta kończy okres współpracy grupy z EMI. Nowym wydawcą zostaje GUN records związana z BMG. Wydaje się, że okres eksperymentów grupa ma za sobą. Płyty Symbol of Life i Paradise Lost są nieco mniej odważne, lecz starają się odnaleźć swoistą syntezę elektronicznych sympatii grupy z brzmieniami z płyty Draconian Times. Po płycie Symbol of Life zespół rozstaje się z Lee Morrisem. Jako perkusista sesyjny dołącza do grupy Jeff Singer, który wkrótce ustępuje miejsca Adrianowi Erlandssonowi.
