В 1998-м с Лабонте пришлось расстаться (он ушел организовывать "All That Remains"), а на его место ангажировали Брайана Феэ из Outcast. Пока Shadows Fall гастролировали, на них положили глаз парни из Century Media, и в 1999-м группа получила нормальный контракт.
Первый же опус, вышедший под новой крышей, ознаменовал смену направления. Брутальная составляющая теперь пошла на спад, а на первое место стали выходить мелодии. Кроме того, если раньше в песнях SF звучал в основном гроулинг, то на "Of One Blood" он был изрядно разбавлен чистым вокалом. После выхода диска в коллективе возникли кое-какие разногласия, в результате чего отбыл Гермэйн. На нескольких концертах Shadows Fall выручил давний друг команды Дерек Керсвилл, а к концу 2001-го установку оккупировал Джейсон Биттнер. В сентябре следующего года на свет появился третий альбом, "The Art Of Balance". Название пластинки достаточно точно отражало стилистику работы - ведь музыканты действительно хорошо держали баланс между агрессивным напором и мелодичностью.
Работа, поддержанная уже четырьмя клипами, пробилась в биллбордовский Топ 20, а ее тираж приблизился к 300-тысячной отметке. Наибольшая популярность пришлась на композиции "What Drives the Weak", "Inspiration on Demand", "The Power of I and I", первая из которых была номинирована на "Грэмми" в категории "Best Metal Performance". От сессий "The War Within" остался нереализованный материал, и в 2006-м Shadows Fall решили пустить его в дело. Добавив к нему несколько каверов, музыканты выпустили пластинку "Fallout from the War". Годом раньше в продажу поступил первый DVD "The Art Of Touring: Drunk And Shitty In Every City", куда помимо целого концерта вошли несколько клипов и закулисные сценки.
С "Fallout from the War" группа исполнила свои обязательства перед Century Media, после чего заключила две новых сделки: с Atlantic - для работы в США, и с Roadrunner - за пределами Штатов. В апреле 2007-го команда выпустила альбом "Threads of Life", сопровождающий сингл ("Redemption") к которому был номинирован на "Грэмми".
Последняя работа Shadows Fall - это диск под названием "Retribution", который группа представит российским поклонникам 6 декабря в клубе "ХО", где также исполнит и свои старые вещи. Концерт открывает группа MANIC DEPRESSION.