Die Geschichte von Madeth gray'll begann mit Hisui, Yukina, Shizuru und Hizumi. Hisui (seinerzeit KEI genannt) und Yukina waren die zwei Hauptmitglieder der Band, da sie das ganze Abenteuer von Anfang bis Ende miterlebten. Der erste der beiden schrieb alle Texte und fast alle Lieder mit dem zweiten. Begegnet sind sie sich dank Shizuru, der mit Hisui bei Vierge und mit Yukina (damals noch Gitarrist) bei L~CYFER gewesen war. Anfangs hatten sie noch keinen Schlagzeuger, was sie allerdings nicht davon abhielt, zwischen Anfang November und Ende Dezember vier auf 300 Stück limitierte Demotapes zu veröffentlichen.
Anfang 1998 war das Line-up noch immer dasselbe, abgesehen davon, dass KEI sein Pseudonym aufgab und sich wieder Hisui nannte. Der März war wieder erfolgreich für die Band, da sie in einer Woche drei Demotapes herausbrachten, gefolgt von einem weiteren am 4. April. Nun, langsam aber sicher von Erfolg gezeichnet, sollten sie im Mai 1998 gleich zwei Schicksalsschläge treffen.
Zuerst starb hide, einer der größten Musiker, die Japan je hervorgebracht hatte. Das zweite Drama betraf Madeth gray'll schließlich direkt, als ihr Gitarrist Hizumi am Tag von hides Beerdigung bei einem Autounfall ums Leben kam. Ironischerweise nannte sich seine vorherige Gruppe vie eternele (frz.: ewiges Leben).
Die Gruppe erholte sich wieder, beschloss, ihre Tätigkeiten fortzusetzen und nahm ihren ersten Schlagzeuger in die Band auf: Tsubaki. Mit ihm erwiesen sie ihrem Freund die letzte Ehre, indem sie eine CD mit einem Lied neu aufnahmen, das er einige Monate vor seinem Tod geschrieben hatte: "Hakuchu yume no sangeki". Diese CD kam in einer schwarzen und in einer weißen Version heraus und wurde auf ihren Lives am 8. und 9. August verteilt, bei denen sie ebenfalls ihr PV zu "Parasite" darboten. Um ihre Rückkehr zu manifestieren, veröffentlichten sie am nächsten Tag ihre erste richtige Single "Juujika no ketsumatsu".
Leider ging es der Band in den darauf folgenden Monaten nicht sonderlich gut und sowohl Shizuru als auch Tsubaki gingen, was Hisui und Yukina alleine zurückließ. Aber der Kern von Madeth gray'll ließ sich dadurch nicht unterkriegen und beendete dieses verfangene Jahr mit der Veröffentlichung des Videoclips "Rasen kaiden to kioku".
1999 war das Jahr der Erneuerung für die Gruppe, denn ein gewisser KISAKI hatte ein neues Label gegründet, das Anfängern helfen sollte. Glücklicherweise wurden Madeth gray'll entdeckt und man fand sie auf der ersten Matina-Compilation "New age culture" wieder. Nachdem beschlossen worden war, die Band wieder aufzubauen, wurde Izumi als Gitarrist eingestellt. Er war vorher bei Distray und hatte dort an der Seite von Ruiza gespielt, den KISAKI später bei Syndrome dabei hatte und den man heute bei D wiederfindet.
Mit Izumi zusammen nahmen sie eine neue Single auf, die dann am 30. Juni erschien. Eine weitere wurde bei ihrem Konzert am 9. August 1999 verteilt, das sie zusammen mit einem weiteren neuen Gitarristen, Ukyou, gaben. Dieses Datum schien kein sehr glückliches für sie zu sein, denn auch Ukyou blieb nicht sehr lange in der Band.
2000 wurde wieder ein besseres Jahr für sie und brachte auch Matina eine erfolgreiche Zeit. Mit dem neuen Schlagzeuger Reika, der ihnen im Oktober beigetreten war, veröffentlichten sie ihr erstes Album "Lucifer", das so erfolgreich war, dass es drei Mal neu aufgelegt wurde. Madeth gray'll traten in diesem Jahr mit dem Session-Gitarristen Airi auf, für den es die erste Band war, in der er spielte.
Dennoch wurde es für Yukina, wahrscheinlich auch durch die bisherigen Rückschläge, ermüdend und er beschloss, die Band zu verlassen. Die anderen Mitglieder wollten nicht ohne ihn weitermachen und so trennte sich die Gruppe. Bei dem Konzert am 28. November, während dem auch noch eine extra Single verkauft wurde, gab Hisui diese Entscheidung öffentlich bekannt. Dennoch erschien am folgenden Tag ihr Mini-Album "Boukai no mato -Entith de marge-" und Airi wurde für die wenigen Wochen, die der Gruppe noch blieben, zum offiziellen Bandmitglied ernannt.
Am 29. Januar 2001 trennten sie sich endgültig während eines Lives und boten ein Live-Video zur Veröffentlichung ihres Memorial-Albums an, das schließlich am darauf folgenden Tag erschien.
