История Pain of Salvation берет свое начало в 1984 году, когда в небольшом шведском городке Eskilstuna 11-летний вокалист и гитарист Daniel Gildenlow собрал свою первую группу – Reality. Единственным участником группы, чье имя не поглотила пучина забвения, стал гитарист Daniel Magdic, который продержался там вплоть до переименования в Pain of Salvation и записи дебютного альбома. В 1987 году группа приняла участие в музыкальном конкурсе «Rock-SM» – том самом, победа в котором принесла славу группе Europe в 1982 году. Reality оказались самой молодой группой на конкурсе, а Гильденлёв был признан лучшим вокалистом.

В 1990 году группу ждали изменения в составе: за барабаны сел Johan Langell (ему тогда было 14 лет), а бас-гитаристом стал Gustaf Hielm. В следующем году Гильденлёв решил переименовать группу в Pain of Salvation. По его словам, такое название символизировало баланс, равновесие хорошего и плохого, двусторонность всего, что есть в нашем мире. В течение следующих трех лет группа завоевала некоторый успех у себя на родине, выигрывая в различных музыкальных конкурсах. Тогда были написаны многие песни, которые впоследствии появились на первых альбомах группы.

В 1994 году Kristoffer Gildenlow (младший брат Даниэля) заменил Густава Хильма, который позже стал членом не менее известной шведской группы Meshuggah. Вскоре после этого Pain of Salvation записали свое первое демо «Hereafter» и разослали его различным рекорд-лейблам. Демо была записано без клавишных, но музыканты чувствовали острую потребность в них и поэтому начали поиски клавишника. Однако случилось так, что он сам нашел их – [aritst]Fredrik Hermansson услышал у приятеля «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 год начался с ухода Даниэля Магдика и замены его Johan Hallgren, который некоторое время играл с Магдиком в группе Crypt of Kerberos. Поскольку Халльгрена приняли в группу непосредственно перед записью нового альбома и у него не было времени разучивать материал, Даниэль Гильденлёв рассчитывал сам записать все партии гитары, но Йохан удивил всех, выучив все песни в течение трех недель, и, в конце концов, сам записал свои партии. Новый альбом «One Hour by the Concrete Lake» был выпущен в июле 1998-го на Avalon в Азии и принес группе большой успех. Слава Pain of Salvation дошла до Европы, и, в итоге, группа подписала контракт с InsideOut Music и InsideOut Music America. В мае 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 февраля 2006 Кристоффер Гильденлёв был уволен по причине безразличного отношения к группе: он не приходил на репетиции, отстранился от остальных участников и больше занимался своим сольным проектом.

В середине 2006-го группа приступила к записи нового альбома «Scarsick». Партии бас-гитары были записаны Даниэлем, а нового басиста Pain of Salvation взяли уже после выхода альбом – им стал Simon Andersson. «Scarsick» был выпущен 22 января 2007 года и стал, пожалуй, самым экспериментальным альбомом группы – его музыкальный материал варьируется от рэпа до диско. Вскоре поклонники узнали, что «Scarsick» – не что иное, как «The Perfect Element, Part 2». Именно эту надпись можно разглядеть на внутренней стороне обложки диска. Позже это подтвердил и сам Гильденлёв.

Концерт в Амстердаме 2 марта 2007 был записан для DVD, который вышел в начале 2008 года. 29 апреля 2007 было официально объявлено об уходе из группы Йохана Лангелля – по его словам, он не мог больше ездить на гастроли и целыми днями пропадать на репетициях, так как хотел полностью посвятить себя семье. Лангелль отыграл последние концерты с группой в 2007 году.

25 февраля 2008 года состоялось первое в истории группы выступление в Росии - в московском клубе «Апельсин». Настоящим сюрпризом для присутствовавших стало исполнение «Ashes» на русском языке под аккомпанемент балалаек.