In order to unlock the characters in the game, play through the story mode's various scenarios. As you progress, you'll unlock different characters, usually after defeating said character or playing as said character.

Unlockable	How to unlock
Chiyo	Beat Itachi Uchiha in The Tale of Naruto Uzumaki
First Hokage	Defeat Sasuke for the first time in the Tale of Young Naruto Uzumaki.
Haku	Defeat Sasuke in the Tale of Zabuza Momochi and Haku.
Haku (Mask)	Defeat Naruto in the Tale of Zabuza Momochi and Haku.
Jiraiya	Win the first battle in A Tale of Jiraiya and he will be unlocked
Kabuto	Defeat Kabuto in the Tale of Young Naruto Uzumaki.
Kabuto (Snake cape)	Complete The Tale of Madara Uchiha
Kakashi (Lightning Blade: Twin Lightning Shiver)	Defeat Kakashi for the second time in the Tale of Zabuza Momochi and Haku.
Kid Kakashi	Beat Minato in The Tale of Kakashi Hatake
Killer Bee	Complete The Tale of the Killer Bee
Kimimaro	Defeat Kimimaro in the Tale of Young Naruto Uzumaki.
Minato Namikaze	Beat Jiraya in The Tale of Minato Namikaze
Minato Namikaze(Hokage)	Beat the Third Hokage in The Tale of Minato Namizake
Obito Uchiha	Beat him with Young Kakashi in the Tale of Kakashi Hatake
Pain	Defeat Naruto(Sage) in The Tale of Madara Uchiha
Part 1 Shikamaru Nara(Chunin Outfit)	Beat Kimimaro in The Tale of Young Naruto Uzumaki
Second Hokage	Defeat Sasuke for the second time in the Tale of Young Naruto Uzumaki.
Third Hokage	Defeat Orochimaru in the Tale of Young Naruto Uzumaki.
Tsunade	Win the second battle in A Tale of Jiraiya and she will be unlocked
Zabuza	Defeat Kakashi for the first time in the Tale of Zabuza Momochi and Haku.