Mystical Ninja Starring Goemon (がんばれゴエモン〜の〜 Ganbare Goemon: Kurofune Tō no Nazo, lit. "Go Goemon: Mystery of the Black Ship Gang") is a Goemon series Game Boy game released in 1998. 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. They 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.