В 1999 году группу покинул клавишник Panayotis, и на его место пришел George.

На протяжении всей своей истории, Rotting Christ множество раз подвергались нападкам из-за своего названия и в ноябре 1999 года даже привлекли внимание международной прессы: во время предвыборной президентской компании в США кандидат от республиканской партии Gary Bauer обвинил группу в том, что они анти-католики. В ответ на критику Bauer, Sakis Tolis написал:

"Живя в (так называемых) демократических обществах, я думаю каждый имеет право говорить о религии, как он/она того хочет. Мы же на самом деле считаем, что они "гниют"! Мы не являемся "сатанистами-крестоносцами", а скорее, как и многие другие группы, представляем темную сторону металла."

Следующим шагом стала работа над новым альбомом. Запись "Sleep of the Angels" снова проходила в Woodhouse Studios, а издан он был в марте 1999 года. "Sleep of the Angels" - это еще один шаг вперед для Rotting Christ. На этом альбоме появилось еще больше готических элементов, но он все еще остался металлическим альбомом, с первой и до последней его секунды.

За две недели до выхода полноформатника был издан EP "Der Perfecte Traum", который содержал 7 треков. Среди них был одноименный трек, взятый с грядущего альбома "Sleep of the Angels", "Moonlight" - не издававшийся ранее трек, который не входил ни в один другой релиз, и 5 концертных записей (с соответствующим звуком), записанные во время выступления в Польше (совместный с Samael и Moonspell европейский тур 1996 года). Этот релиз был очень хорошо принят фанатами группы, особенно в Германии. "Der Perfecte Traum" стал первым релизом, на котором была представлена песня на языке, отличном от английского (одноименная, собственно, песня), не считая нескольких старых треков на латыни. К тому же, первоначально предполагалось, что вокальные партии для этой песни исполнит фронтмен известной группы Rammstein, Till Lindeman, которого впоследствии все же заменил некий Eddy Kante.

Реакция фанатов снова была ошеломительной, и аудитория Rotting Christ выросла в разы. Некоторые из старых поклонников все еще обижались на то, что группа продолжает сочинять музыку, которая слишком отличается от их старого материала, но при этом кое-кто из них смог отыскать элементы старого-доброго black metal в треках вроде "The World Made End" или "Delusions".

"Sleep of the Angels" стал альбомом, который привел Rotting Christ к их первому мировому турне. Вначале был массивный европейский тур с Deicide, Ancient Rites, Aeternus и Behemoth. Потом группа отправилась в США для тура по куче городов. Как позже вспоминал Sakis Tolis:

"Самый первый наш тур по США, который прошел еще в 90-х, вышел очень необычным. В нем участвовала только наша группа, мы проехались по всему континенту и вели машину сами, не зная ничего. У нас даже не было водительских прав при себе. Но это было давно. Сейчас же с каждым разом все становится все лучше и лучше. Люди здесь привыкают к европейским группам, и мы довольны тем, что наконец-то может встретить здесь людей, которые полностью поддерживают Rotting Christ."

После тура по США группа отправилась покорять страны Латинской Америки вроде Колумбии и Бразилии, где их преданные поклонники продемонстрировали небывалую активность на каждом шоу. В Мексике группа пережила достаточно сильное землетрясение (6,8 баллов), в результате которого Themis получил незначительные травмы, а все остальные отделались испугом.

Позднее группа вернулась в Грецию, чтобы завершить мировой тур особенно удачным шоу в афинском Rodon Club (на этот раз с кристально чистым звуком) и небольшим туром по прочим городам. На этом выступлении в Rodon Club старый друг группы, Gunther Theys (басист/вокалист Ancient Rites) исполнил припев в песне "The Sign Of Evil Existence". Кроме того, этот концерт посетил известный греческий художник и иллюстратор Vasilis Arnaoutoglou, который под впечатлением от увиденного и услышанного предлагает Sakis'у сделать видеоклип на одну из композиций Rotting Christ. В результате этого сотрудничества появился первый официальный видеоклип группы, "After Dark I Feel". Это довольно уникальное видео, так как оно не содержит кадров с самой группой, но при этом является видеорядом, который максимально удачно визуально представляет этот трек.