Era de Gackt
En 1995, tras casi un año lejos de los escenarios, Malice Mizer incorporó a Gackt como nuevo vocalista. Bajo su influencia, el estilo del grupo se volvió más nostálgico y romántico, con una mayor influencia tanto de la música clásica como de la música pop francesa. En cuanto a su vestuario, la banda abandonó su estilo gótico por coloridos trajes históricos con una mayor influencia de la estética visual kei.
El 10 de diciembre fue publicado su primer sencillo, y su primer trabajo musical con el nuevo vocalista Gackt, «Uruwashiki Kamen no Shoutaijou», el sonido de este sencillo es totalmente diferente a sus trabajos anteriores es en donde se puede apreciar una fuerte influencia de la música pop francesa, el sencillo contiene la versión en japonés de la canción “Après Midi ~Aru Pari no Gogo De~”, la versión en inglés fue publicada en el ómnibus álbum Shock Wave '96 y en una cinta de demostración repartida durante eventos públicos. No se tienen registros de listas de las ventas de este sencillo.
Voyage ~Sans Retour~
En junio de 1996, Malice Mizer lanzó al mercado su segundo álbum, Voyage ~sans retour~, según declaraciones de los miembros de la banda el estilo musical del álbum era como "un retorno a la infancia" durante dos años se realizaron presentaciones por todo Japón promocionando su nuevo sencillo y el álbum. Malice Mizer estaba logrando un gran reconocimiento entre el público y los medios. El 10 de octubre se publicó el segundo sencillo «Ma chérie ~Itoshii kimi e~» como celebración del primer aniversario de Gackt como vocalista de la banda, y como inauguración de su club de fanáticos oficial, también llamado «ma chérie».
Nippon Columbia y merveilles
La popularidad de la banda creció y en 1997 firmaron un contrato con el importante sello discográfico Nippon Columbia, con el que editaron un gran número de exitosos sencillos, un cortometraje (Verte Aile, también llamado Bel Air de l'image); y, en 1998, su primer y último álbum con esa discográfica, merveilles.
También tuvieron su propio programa de radio y revista. En enero de 1999, en pleno apogeo de la banda, Gackt la abandonó para empezar su carrera como solista. Malice Mizer rompió su contrato con Nippon Columbia y volvió a la firma de música indie de Mana, Midi:Nette.
Muerte de Kami y Periodo sin Vocalista
Unos meses después de la retirada de Gackt, el baterista Kami murió a causa de una hemorragia subaracnoidea.
Su cuerpo fue descubierto cuatro días después. Pero a pesar de esto, su funeral se realizó ese mismo día con la asistencia de los miembros de su banda (Mana , Közi y Yu~ki), sus padres y algunos amigos cercanos. Gackt, quien comenzaba su carrera solista, se encontraba de gira en ese momento y no se enteró de la muerte de su querido amigo hasta la siguiente semana. Al tomar conocimiento de lo sucedido quedó devastado por largo tiempo.
Meses antes de su muerte, Kami había compuesto y escrito 3 canciones: "Unmei no Deai", "Mori no naka no tenshi" y "bara no souretsu". Unmei no Deai y Mori no naka no tenshi vieron la luz en el box set en honor a él llamado "Shinwa". Mientras que bara no souretsu fue incluido como secret track en el single Beast of Blood.
