Nel 2000 Kenichiro Fukui e Tsuyoshi Sekito, entrambi impiegati della SquareEnix, danno inizio a una collaborazione sperimentale che porta alla composizione di musiche in stile rock per il videogioco All star Pro-Wrestling. Anche dopo il successo del videogame, i due continuano a comporre, e nel 2002 decidono di arrangiare, sempre in stile rock, alcune composizioni di Nobuo Uematsu. Il compositore, da sempre appassionato di musica rock, apprezza molto il lavoro fatto da Fukui e Sekito, e decide di fondare con loro il gruppo dei Black Mages.

Nel 2003 Fukui e Sekito, con la collaborazione di Uematsu, arrangiano e interpretano 10 pezzi tratti dai vari capitoli di Final Fantasy, tutti dedicati alle battaglie, pubblicati nell'album The Black Mages, edito il 19 febbraio dello stesso anno. L'album ha molto successo, così viene organizzato il primo concerto, a cui partecipano diversi membri di SquareEnix: Keiji Kawamori al basso, Michio Okamiya alla chitarra, Arata Hanyuda alla batteria, oltre naturalmente a Fukui e Sekito, rispettivamente alla tastiera e Sekito alla chitarra. Inoltre, anche Uematsu viene convinto a suonare con la band, e comincia a suonare anche lui la tastiera insieme al gruppo. Il primo concerto della band si tiene il 26 aprile 2003 a Tokyo, e sarà seguito da una performance di 30 minuti il 3 novembre in occasione del festival della Kanagawa university.

Nell'aprile 2004 i Black Mages partecipano ad un album dal titolo Dark Chronicle Premium Arrange, che contiene arrangiamenti di pezzi del videogioco Dark Cloud 2. Nel dicembre dello stesso anno viene pubblicato l'album The Black Mages II: the Skyes Above, che contiene, diversamente dal primo, molti temi tratti da Final Fantasy, ma non di battaglia. Nell'album ci sono inoltre due canzoni, il cui testo è stato scritto da Alexander O. Smith, il traduttore di Final Fantasy X e XII. Si tratta di Otherworld, eseguita dalla cantante Kazco Hamano, e di The Skyes Above, cantata da Tomoaki Watanabe (noto come mr. goo). Nel pezzo Maybe I'm a Lion, invece, la voce che si sente all'inizio è dello stesso Smith.

Ancora una volta, all'album sono seguiti tre concerti, tenuti a Kanagawa e a Osaka.

Inoltre, il 16 maggio 2005, il gruppo si è esibito negli Stati Uniti, a Los Angeles, con il concerto More Friends.

I Black Mages hanno partecipato inoltre alla colonna sonora del film SquareEnix Final Fantasy VII: Advent Children, interprentando il tema Advent: One-Winged Angel, con l'orchestrazione di Koji Haijima.

Secondo Uematsu presto verrà pubblicato un terzo album, con allegato un cd extra, centrato sulla mitologia giapponese.