История Pain of Salvation берет свое начало в 1984 году, когда в небольшом шведском городке Эскильстуна 11-летний вокалист и гитарист Даниэль Гильденлёв собрал свою первую группу под названием Reality. Единственным участником группы, чье имя не поглотила пучина забвения, стал гитарист Даниэль Магдик, который продержался там вплоть до переименования в Pain of Salvation и записи дебютного альбома. В 1987 году группа приняла участие в музыкальном конкурсе Rock-SM — том самом, победа в котором принесла славу группе Europe в 1982 году. Reality оказались самой молодой группой на конкурсе, а Гильденлёв был признан лучшим вокалистом.
В 1990 году группу ждали изменения в составе: за барабаны сел Йохан Лангелл (ему тогда было 14 лет), а бас-гитаристом стал Густав Хильм (который вернулся в группу в 2011 году). В следующем году Гильденлёв решил переименовать группу в Pain of Salvation. По его словам, такое название символизировало баланс, равновесие хорошего и плохого, двусторонность всего, что есть в нашем мире. В течение следующих трех лет группа завоевала некоторый успех у себя на родине, выигрывая в различных музыкальных конкурсах. Тогда были написаны многие песни, которые впоследствии появились на первых альбомах группы.
В 1994 году Кристоффер Гильденлёв (младший брат Даниэля) заменил Густава Хильма, который позже стал членом не менее известной шведской группы Meshuggah. Вскоре после этого Pain of Salvation записали свое первое демо Hereafter и разослали его различным рекорд-лейблам. Демо-запись была записана без клавишных, но музыканты чувствовали острую потребность в них и поэтому начали поиски клавишника. Однако случилось так, что он сам нашел их — Фредрик Германссон услышал у приятеля Hereafter и попросил познакомить его с этой группой. Так осенью 1996 года в Pain of Salvation появился клавишник.
В начале 1997 года Pain of Salvation приступили к записи своего первого альбома Entropia в шведской Roasting House Studio. В августе того же года альбом был выпущен в Азии на Avalon — дочернем лейбле Marquee. Пластинка получила хорошие отзывы в прессе, и в Marquee решили заняться раскруткой альбома в Японии. Благодаря Интернету Entropia стала известна в Европе, и вскоре группа подписала еще один контракт — с румынским лейблом SC Rocris Discs. В Европе альбом был выпущен только в 1999 году, когда уже достаточно известных Pain of Salvation взял под крыло крупный лейбл InsideOut Music. Тогда же альбом был выпущен в Южной Америке на Hellion Records.
1998 год начался с ухода Даниэля Магдика в связи с разносторонними взглядами на музыку и замены его Йоханом Халлгреном, который некоторое время играл с Магдиком в группе Crypt of Kerberos. Поскольку Халлгрена приняли в группу непосредственно перед записью нового альбома и у него не было времени разучивать материал, Даниель Гильденлёв рассчитывал сам записать все партии гитары, но Йохан удивил всех, выучив все песни в течение трех недель, и, в конце концов, сам записал свои партии. Новый альбом One Hour by the Concrete Lake был выпущен в июле 1998-го на Avalon в Азии и принес группе большой успех. В мае 1999 второй альбом был выпущен в Южной Америке, а группа отправилась в турне по Европе вместе с Threshold и Eldritch. 19 ноября Pain of Salvation успешно выступили на фестивале ProgPower в Нидерландах.
К записи концептуального альбома The Perfect Element, Part 1 группа приступила в марте 2000-го, а выпущен он был в октябре того же года. Осень Pain of Salvation провели в турне по Европе, а в феврале 2001-го дали свой первый концерт в США — в качестве лидеров фестиваля ProgPower USA.
В конце 2001-го Pain of Salvation записали свой четвертый альбом Remedy Lane, который попал в магазины уже в январе 2002-го и снова вызвал восторженные отзывы в прессе. В Remedy Tour сами Dream Theater позвали Pain of Salvation выступать у них на разогреве. Группа уверенно ступила на Олимп прогрессивного металла.
12 марта 2003-го Pain of Salvation дали полностью акустический концерт в родном городе Эскильстюна, который был записан и выпущен в начале 2004 года как концертный альбом 12:5. Песни со всех четырех альбомов группы были аранжированы в совершенно ином ключе и сильно отличались от оригинала. 12:5 получился скорее новым альбомом, нежели просто концертником со старым материалом.
В 2003 году группа приступила к работе над самым амбициозным, самым масштабным своим проектом. Даниель Гильденлёв разрабатывал концепцию BE с 1996 года, и к 2003-му этот почти философский труд о существовании Бога, судьбе человечества, о бытии в целом обрел окончательную форму. Перед записью группа дала несколько концертов в Эскильстюне, где полностью исполняла BE с костюмированными постановками, декорациями, с большим экраном на сцене и специально приглашенным оркестром из девяти человек The Orchestra of Eternity. В феврале 2004 года началась запись BE, а уже в сентябре он попал в руки меломанов. Альбом произвел фурор во всем мире, став настоящим шедевром с своем жанре. В 2005-ом был выпущен DVD и концертный альбом BE (Original Stage Production), содержавший запись одного из тех театрализованных выступлений в Эскильстюне.
К 2005 году у группы появились фан-клубы в Германии, Франции, Греции, Нидерландах и США, а многие признанные классики прогрессивного рока называли Pain of Salvation одной из своих любимых групп. Тогда же Даниель Гильденлёв заявил, что группа не посетит более США, так как, по его мнению, снятие отпечатков пальцев у иностранцев перед въездом в эту страну ущемляет его права. 21 февраля 2001 Кристоффер Гильденлёв ушел из группы по причине безразличного отношения: он не приходил на репетиции, отстранился от остальных участников и больше занимался своим сольным проектом. Переехав в Нидерланды со своей женой, он участвовал в записи группы Dial.
В середине 2006-го группа приступила к записи нового альбома Scarsick. Партии бас-гитары были записаны Даниелем, а роль нового басиста Pain of Salvation после выхода альбома занял Саймон Андерссон. Scarsick был выпущен 22 января 2007 года и стал, пожалуй, самым экспериментальным альбомом группы — его музыкальный материал варьируется от рэпа до диско. Вскоре поклонники узнали, что Scarsick — ни что иное, как The Perfect Element, Part 2. Именно эту надпись можно разглядеть на внутренней стороне обложки диска. Позже это подтвердил и сам Даниэль.
Концерт в Амстердаме 2 марта 2007-го был записан для DVD, который вышел в начале 2008 года. 29 апреля 2007-го было официально объявлено об уходе из группы Йохана Лангелля — по его словам, он не мог больше ездить на гастроли и целыми днями пропадать на репетициях, так как хотел полностью посвятить себя семье.
Настоящем событием стал концерт группы в Москве, 25 февраля 2008 года в клубе Апельсин. Выступление было впечатляющим, Даниель приятно удивился такой отдаче от публики и обещал вернуться как можно скорее.
Летом 2009 появилась первая информация о грядущем альбоме, выпуск которого задержало банкротство звукозаписывающей компании SPV, под чьим руководством находится прогрессивный лейбл InsideOut Music. Но лейбл был быстро куплен компанией Century Media, что позволило продолжать запись альбома. 3-го сентября стало известно название нового альбома Road Salt с запланированным релизом в начале 2010 года. Так же 14-го ноября состоится релиз EP Linoleum с 5 новыми треками и один кавер Yellow Raven (Scorpions). В конце января был выпущен видеоклип на песню Linoleum. В связи с расширением концепции альбома было принято решение разделить его на две части: Ebony и Ivory.
17 мая 2010 вышла первая часть Road Salt с измененным названием — Road Salt One. Даниэль Гилденлёв описал этот альбом как джемовый, будто некоторые песни были записаны живьём в репетиционной комнате. Концепция Road Salt заключалась нескольких параллельных историях (не вымышленных и не автобиографических), где главная смысл — выбор, который люди делают в своей жизни.
30 марта 2011, перед выходом второй части Road Salt был снят видеоклип на песню Where It Hurts, который содержал интимные, по мнению YouTube, сцены и был быстро заблокирован и исправлен.