Нарешті в 1991 році, остаточно визначившись із напрямком, назва банди поміняли на більш підходяще, "Novembers Doom". Група записала демо з двома піснями, за допомогою якого справила враження на італійський лейбл "Avantgarde Records".
У 1995 році цією фірмою був випущений дебютний альбом "Amid It s Hallowed Mirth". Слідом за цим "Novembers doom" розлучилися з Джимом Доблескі, замінивши його Джо Хернандес, а також дістали в свої ряди бас-гітаристка Мері Біліч, ветераншу таких команд як "Master mechanic", "Mythic", "Wormhole" і "Derketa".
Минуло ще трохи часу, і кадрові флуктуації продовжилися. Новим гітаристом став Ерік Бернлі, а за ударні сів Аббас Джаффарі. Солідно оновлений склад у 1997 році записав трехтрековий EP "For Every Leaf That Falls", що отримав непогані відгуки в пресі. На наступний рік "Novembers Doom" взялися за сесії другого повнометражного альбому "Of Sculptured Ivy And Stone Flowers". Продюсувати платівку запросили гітариста "Broken Hope" Брайана Гріффіна, з яким Пол і Мері співпрацювали в сайд-проекті "Em Sinfonia". Цим альбомом група довела, що грати дум вміють не тільки європейці, чиєю прерогативою до цих пір вважався цей стиль.
Але позитивні відгуки на "Of Sculptured Ivy And Stone Flowers" не врятували колектив від плинності. Після виходу диска місце ударника зайняв Джо Нунез, а другу гітару взяв у руки Ларрі Робертс з "Dead Serenade". У 2000 році "Novembers Doom" перейшли під дах "Dark Symphonies" і знову відправилися в студію, взявши в продюсери Кріса Дьюрісека.
Альбом "The Knowing" продовжив обрану генеральну лінію і також мав хороші огляди. Диск цей був виданий і в Європі за допомогою "Pavement Music". У тому ж році "Dark Symphonies" перевидала дебютний лонгплей з додаванням декількох бонусних треків. У 2001-му Мері Біліч пішла з "Novembers Doom" в "Penance", і перед групою знову постала кадрова проблема. Постійну заміну Мері відразу знайти не вдалося, і тому на сесіях "To Welcome The Fade" були присутні два гостя-четирехструнщіка, Брайан Гордон і Рон Холзнер.
Продюсував нову роботу "ноябрістов" володар "Греммі" Ніл Кернон (раніше співпрацював з "Kansas", "Yes", "Queensryche", "Judas Priest", "Nevermore", "Cannibal Corpse"), який допоміг добитися команді за цим чистого і потужного звучання. Вже за традицією музичні успіхи колективу незмінно супроводжувалися чехардою складу. Після "To Welcome The Fade" і до 2004 року в команді змінилося два басиста і два гітариста.