W 1997 roku grupa wznowiła działalność w składzie poszerzonym o gitarzystę Piotra Ostrowskiego. Rok później grupa w olsztyńskim Selani Studio zarejestrowała demo pt. ...Now is Forever. Niedługo potem grupę opuścił Tomasz Fornalski którego zastąpił znany z występów w grupie Shemhamforash basista Krzysztof Artur Zagórowicz. W tym czasie zespół wznowił działalność koncertową występując wraz z Dying Fetus, Monstrosity oraz Kataklysm ponadto Lost Soul wystąpił na festiwalach Obscene Extreme Festival i Silesian Open Air. Rok później demo pt. ...Now is Forever ukazało się na kompilacji Disco's Out, Slaughter's In nakładem wytwórni Novum Vox Mortis oraz na Polish Assault wydanej rok później przez Relapse Records. thumb|200px|left|Piotr Ostrowski – były gitarzysta Lost Soul podczas koncertu, 11 września 2005 roku W roku 2000 wydany został pierwszy studyjny album grupy pt. Scream of the Mourning Star. W Polsce wydany przez Metal Mind Records. Na świecie płyta ukazała się dzięki Relapse Records. Album spotkał się z entuzjastycznym przyjęciem zarówno fanów jak i krytyki. W maju 2002 roku grupa podpisała kontrakt płytowy z polską wytwórnią Empire Records opiewający na wydanie drugiej płyty pt. Ubermensch (Death of God).