Крім них на сесіях гостювали вокалістка Карина Кьеллберг (вона також була присутня і на наступних альбомах), гітарист Матіас Ла Еклунд з "Freak Kitchen" і кінгдаймондовец Енді Ла Рок, який виступив також в ролі продюсера.
Для наступного релізу "Evergrey" перебазувалися на готичний лейбл "Hall Of Sermon". Сесії проходили без клавішника, але зате серед "гостьових" інструментів були присутні арфа і скрипка, а крім цього був запрошений хор з католицької церкви.
Презентація "Solitude, Dominance, Tragedy" проходила в німецькому місті Бохумі в компанії музикантів з "Rage". Потім колектив вирушив на європейські гастролі в компанії з "Kamelot" і "Crimson Glory", а також взяв участь у фестивалі "Bang Your Head", що проходив в Німеччині. У тому ж році група знайшла час на запис композиції "Rising Force" для триб'юту Інгві Мальмстін. Трохи пізніше команду покинули басист Даніел Нойд, що поступився своє місце Майклу Хаканссону і гітарист Ден Бронелл, замінений Хенріком Данхеджем.
Крім того, група поповнилася клавішником Свеном Карлссоном. Оновлений склад уклав контракт з лейблом "Inside Out Music" і в 2001 році відправився на сесії. Що вийшов в жовтні концептуальний альбом "In Search Of The Truth" приніс групі перший значний успіх, зайнявши в шведських чартах 59-у позицію.
А текучка кадрів все одно тривало. Спочатку Свена Карлссона змінив Кріс Рен, а в 2002 році місце за клавішними зайняв Рікард Зандер. У вийшла конфігурації був записаний альбом "Recreation Day", причому продюсував вже не Енді Ла Рок, а Енглунд з Данхеджем. Після закінчення сесій в "Evergrey" з'явився новий ударник - Йонас Екдал. Його перша перевірка на міцність відбулася в короткому, але досить інтенсивному американському турі, де "вечносерие" з'явилися в компанії "Arch Enemy", "Hate Eternal" і "The Black Dahlia Murder".
Гастрольна діяльність продовжилася і на наступний рік, коли "Evergrey" відіграли серію концертів в Данії разом з "Mercenary", а потім знову вирушили в Штати, де їм довелося розігрівати "Iced Earth" і "Children Of Bodom". Новинка від шведських металістів з'явився в травні 2004 року, почавши свій шлях з 24-го рядка шведських чартів.