Mystical Ninja Starring Goemon (がんばれゴエモン〜黒船党の謎〜 Ganbare Goemon: Kurofune Tō no Nazo?, "Go Goemon: Mystery of the Black Ship Gang"), is a Ganbare Goemon series game released in 1998 for the Game Boy handheld console system. Featuring gameplay similar to the Super Famicom title Ganbare Goemon 3: Shishijūrokubē no Karakuri Manji Gatame, the game presents a new story in which Yae has been kidnapped by the Black Ship Gang. Its release immediately followed the Nintendo 64 game of the same name.
After Yae is kidnapped, Goemon, Ebisumaru, and Sasuke set out to find the Black Ship Gang and rescue her. They first assault Karakuri Castle, the pirates' hideout, where they learn that Baron Skull, the captain of the group, lured Yae to his hideout. They pursue Baron to the Demon Cave, where Goemon discovers clues left behind by the female ninja. These take him to the Black Ship Skull, the flagship of the pirates moored in Gull Harbor. Goemon and his friends destroy the ship without locating Yae, and are aghast to see a second Black Ship Gang vessel sail into harbor. They board it and continue the quest, eventually wresting Yae from Baron Skull's hold.
Mystical Ninja Starring Goemon features three playable characters: Goemon, Ebisumaru, and Sasuke, who can walk, jump, attack, and throw weapons throughout five stages of play. Goemon enjoyed average abilities; Ebisumaru could throw farther but suffered athletically, while Sasuke could jump high but could not throw as well as the others. Players control one character at a time to move through each stage and defeat enemies, who attack with close-range and projectile weapons. At the end of each stage is a boss enemy with higher health and stronger attacks than other foes.
If a player's character is hit by an enemy, his hit points are decreased; if all are exhausted, the character loses a life and the stage is restarted from the beginning. Hit points can be replenished via hearts scattered throughout the game. At maximum hit points, characters are capable of long-range special attacks.
Mystical Ninja features some puzzle elements and mini games, such as fetch quests producing items needed to cross inhospitable terrain or quizzes for bonus items.
The game's music kept with the style of other Ganbare Goemon games by employing an "oriental sound". It is compatible with the Super Game Boy and contains a special decorative border for play in this fashion.
Nintendo Power gave Mystical Ninja Starring Goemon a 6.7 rating on a scale of 1 to 10. The magazine's editors enjoyed the expansive world, but criticized the quality of certain graphical elements, noting that certain hazards and features were "hard to distinguish". The play control received average marks, with Nintendo Power's reviewers decrying the difficulty of dodging due to the high speed of enemy projectiles and movement problems with boss battles. Writers compared the game to The Legend of Zelda series in design, but criticized the automatic regeneration of enemies in each stage, a tenet which made retracing one's steps tedious. The magazine's reviewers noted that Mystical Ninja would provide a challenging experience despite not being as detailed as the Zelda games. Nintendo Power's spotlight on the game concluded with the remarks that players should not "expect to get a smaller version of the N64 game", and that though the minigames were "a blast", "the main game is sort of a drag".