Kolejny okres działalności zespołu obfitował w zmiany składu oraz prace nad nowym albumem. Grupa po raz kolejny skorzystała z Manek Studio i nagrała drugi album zatytułowany „Immortal”. Utwory zawarte na tej płycie były bardziej brutalne, mroczne, a przy tym o mocno progresywnym i technicznym zacięciu. Premiera albumu miała miejsce w 2004 roku, a wydawcą była białoruska wytwórnia The Flaming Arts. Promocja płyty była zakrojona na skalę do tej pory niespotykaną w historii Neolith. Recenzje i wywiady oraz dystrybucja na całym świecie oraz trasy koncertowe: Barbarossa 2 po krajach byłego ZSRR w towarzystwie Behemoth, trasa z Devilyn, Diamanthian, Maple Cross po Finlandii oraz pierwsza trasa w charakterze headlinera po Słowacji razem z Abstract i Return To Innocence. W międzyczasie Neolith występował na Metalmanii, Metal Head's Mission (Krym/Ukraina), Jalometalli (Finlandia) czy Merciless East.