W 1994 roku, Kristoffer Gildenlöw (młodszy brat Daniela) zastąpił Gustafa Hielma (który później dołączył do innego szwedzkiego zespołu Meshuggah) na gitarze basowej. W składzie zawierającym braci Gildenlöw, Daniela Magdica i Johana Langella, zespół nagrał w lokalnym studiu nagraniowym pierwsze demo: Hereafter, które stanowiło połączenie starego i nowego materiału. Pomimo nagrania wcześniej kilku kaset, to demo jako pierwsze zostało porozsyłane do różnych wytwórni płytowych w nadziei na podpisanie kontraktu. Zespół również z pomocą owego dema zaczął poszukiwania klawiszowca. Na odzew odpowiedział Fredrik Hermansson, który jesienią 1996 roku został piątym członkiem Pain of Salvation.
Nagranie i wydanie pierwszego albumu (1996–1997) Dwoma pierwszymi wytwórniami do których zostało wysłane demo były Marquee/Belle Antique (japońska wytwórnia płytowa) i Roasting House (profesjonalne studio nagraniowe w Malmö w Szwecji). Na początku 1997 roku, zespół nagrał debiutancki album Entropia w Roasting House Studio. Album został wydany w Azji nakładem wytwórni Avalon (własność Marquee) w sierpniu 1997 roku, gdzie spotkał się z ciepłym przyjęciem. W rezultacie tego, Marquee zdecydowało się wysłać Daniela do Tokio, gdzie podczas jednego tygodnia w październiku uczestniczył w konferencjach prasowych i udzielał wywiadów dla prasy muzycznej.