Початок історії цієї шведської прогресив-команди було покладено в 1984 році. Тоді 11-річний Даніель Гільденлоу (вокал, гітара) заснував свою першу банду під назвою "Reality". Незважаючи на свій юний вік, хлопці робили цікаву музику, чим привернули до себе увагу шведської преси. У 1987-му "Reality" взяли участь у національному конкурсі "Rock-SM" (з якого в свій час стартували їх земляки з "Europe"), і Даніель отримав там приз як кращий вокаліст.
У 1990-му в команді почалися великі перетасовки. Басиста Магнуса змінив Йоаким, а місце ударника Мікаеля зайняв Йохан Лангелла. Магнус незабаром пішов, передавши бас-гітару Густаф Хелм з "Meshuggah". Починаючи з 1991 року група виступала вже під вивіскою "Pain of salvation".
Колектив брав участь у всіляких конкурсах, і якщо не перемагав на них, то обов'язково пробивався у фінал. У грудні 1994-го басуху замість Хелма взяв у руки молодший братик Даніеля Кристоффер. Група тим часом шукала собі клавішника, але знайти відповідну людину довго не вдавалося, і лише в кінці 1996-го складу "Pain of salvation" був доукомплектований Фредріком Херманссоном.
Покінчивши з кадровими проблемами команда відразу ж відправилася в студію готувати першу демку. У принципі, хлопці і раніше потихеньку записувалися на плівку, але на цей раз було вирішено відправити її на рекорд-лейбли. Відгуки на демо були схвалюють, і вже на початку 1997-го "Pain of salvation" сиділи під дахом "Roasting house" і записували свій перший альбом. "Entropia" був виданий у серпні 1997-го спочатку в Азії. А ось європейцям довелося почекати ще пару років, що не завадило альбому отримати позитивні відгуки. Незадовго до наступних сесій гітарист Даніель Магдік, і до того мав напружені стосунки з Гільденлоу, остаточно посварився зі своїми колегами і грюкнув дверима.
Утворилася дірка вдалося закрити за допомогою Йохана Халлгрен, який зміг за короткий термін вивчити матеріал для "One hour by concrete lake". Якість роботи музикантів на цьому альбомі підвищився, і цей факт призвів до укладення контракту з шановним прогресив-лейблом "Inside Out". Вихід другого диска супроводжувався тритижневим європейським туром і хедлайнерство на фестивалі "ProgPower" в Голландії.
Половину 2000 року "Pain of salvation" провели в роботі над новим матеріалом, легшим в основу "The perfect element: Part 1". Цей концептуальний альбом вийшов у вересні, в той час коли колектив гастролював в Англії разом з "Arena". Протягом того ж туру, коли група виступала в Іспанії, Даніель пошкодив два пальці на лівій руці, проте графік змінювати не стали, і всі концерти були чесно відіграні. На наступний рік "Pain of salvation" багато "фестивалити" - їх можна було побачити на голландській та американському "ProgPower", "Dynamo", "Powermad" та інших подібних заходах.
Черговий альбом задумувався як продовження "The perfect element: Part 1", тобто "Part 2", однак згодом рішення поміняли, і замість цього в 2002-му на світ з'явився "Remedy Lane", абсолютно не пов'язаний з попередником. На початку 2004-го "Pain of salvation" записали акустичний концертний альбом "12:5", а по осені пообіцяли видати черговий студійник з робочою назвою "Be".