Nacido en Kochi en 1972, Naoshi Mizuta empezó a interesarse por la música cuando aún iba a la escuela. Una de sus mayores influencias fue Ryuichi Sakamoto, y aunque estuvo interesado en el mundo musical durante mucho tiempo, decidió estudiar Derecho y Economía en la Universidad de Chiba. Fue en su último año de carrera cuando por fin se decidió a componer algo, una experiencia que le animaría a abandonar el camino que le abrían sus estudios para dedicarse plenamente a la que había sido siempre su gran pasión. Así pues, en 1995 entró en Capcom para cubrir un puesto como compositor de la empresa. Durante su primer año trabajó junto a otros profesionales para realizar el que sería su primer trabajo, la banda sonora del videojuego Street Fighter Alpha.
Los siguientes años los dedicaría a componer y crear versiones en una variada serie de títulos. Por ejemplo, el arcade Dungeons & Dragons: Shadow over Mystara, Darkstalkers 3, Resident Evil 2 o el spin-off Mega Man & Bass. La mayoría fueron trabajos de menor consideración, pero aprendió mucho de esta época como principiante. Más tarde, Mizuta encontró una oferta de trabajo y se presentó en las oficinas de Square para probar suerte. Los entrevistadores se quedaron muy impresionados por su colaboración en Resident Evil 2, y pensaron que sería el candidato perfecto para completar la banda sonora del proyecto que estaban desarrollando en ese momento: Parasite Eve II. El artista trabajó durante año y medio en la composición del juego procurando crear la atmósfera adecuada para el mismo.