When starting to save Mario, Yoshi must walk into the Rec Room and then into the room with the "8" on it. Then, the player must venture throughout the area and find the area to fight Goomboss by going to the vine, going up the bridge and then jumping into the hole where the battle with Goomboss awaits.
When Yoshi fights Goomboss, he must run after him until reaching Goomboss' back. Then, Goombas appear and Yoshi must swallow a Goomba and spit it out at Goomboss' back. Then, he grows mad and tries to attack Yoshi again by, this time, going quicker. This step must be done with a total of three times to defeat Goomboss so he explodes into multiple Goombas and gives up the Mario Key, allowing Yoshi to unlock Mario.
To get the first star, the player must find all eight of the Red Coins by using all sorts of caps for doing different uses with them. This mission cannot be done unless Luigi and Wario are unlocked.
To get the second star, Mario is required as he is the only character having the ability to wall jump. When Mario starts this mission, he must head over to the Star Switch to activate a hidden Power Star in a caged area for a limited time.