Прості меломани так і не змогли ознайомитися з цими піснями, оскільки плівка служила виключно в промо-цілях і за допомогою неї музиканти сподівалися організувати концертну діяльність.
Однак процес йшов туговато, і за наступні три роки команда Мухаммеда просунулася набагато. У студію колектив потрапив тільки в 1995-му, причому склад поповнився гітаристом Маттіасом Хользапфелем. Однойменне демо "Necrophagist", вироблене оновленої конфігурацією, мало більш широкий резонанс і принесло команді популярність у європейському метал-андеграунді.
Концерти колективу стали не таким вже рідкісним явищем, а це в свою чергу вивело "некрофагістов" в лідери прог-детовой сцени. До 1999 року музиканти вже були готові записати повнометражний альбом, що власне вони і зробили. Незважаючи на те що "Onset of Putrefaction" випускався своїми силами і мав обмежений тираж, реліз викликав безліч похвал. Зібравши до купи впливу різних стилів, "Necrophagist" самі стали зразком для наслідування підростаючому поколінню детстеров. Популярність групи значно збільшилася, і музикантів тепер запрошували до себе на розігрів такі монстри брутал як "Cannibal Corpse", "Napalm Death" і "Sinister". Крім того, "некрофагів" засвітилися на низці фестивалів, включаючи німецький "Fuck The Commerce", чеський "Brutal Assault" і американський "Maryland Deathfest".
У 2004 році команда уклала контракт з "Relapse Records" і приступила до запису другого альбому. Склад "Necrophagist" до того часу радикально оновився, а партнерами Мухаммеда стали гітарист Крістіан Мюнзнер, басист Стефан Фіммерс і барабанщик Ганс Гроссманн.
Основний процес підготовки "Epitaph" проходив на німецькій землі (хоча й у різних студіях), а мастерингом займався Боб Катц під флоридської "Digital Domain". За допомогою цієї роботи музиканти встановили нові кордони дез-металу, проте Мухаммед залишався незадоволений попереднім опусом і тому взявся за його переробку. Препарування піддалися практично всі треки, причому в основному це торкнулося партій ударних, які Гроссманн перепрограмував за допомогою драм-комп'ютера. Крім того, в підновляє "Onset of Putrefaction" увійшли дві бонусних композиції, запозичених з демки 1995 року.
На жаль, група ненадовго затрималася під дахом "Relapse", оскільки у музикантів виникли розбіжності з лейблом з приводу заокеанських гастролей. У складі знову почалися флуктуації, і до 2007 року Мюнзнер і Гроссманн поступилися свої місця Самі Раатікайнену і Марко Міннеманну. Незважаючи на всі ці перипетії колектив продовжував гастролювати і в 2008-м зібрався випустити третій альбом.