After Mario defeated Bowser in Super Mario Bros. 3, he and his brother Luigi began to escort Peach back to the Mushroom Kingdom. They were having a nice, safe journey until a Bob-omb fell from the sky! Luigi looked up and to his surprise saw an enemy he had never saw before! It looked like a Lakitu, but it was black with odd eyes. He claimed to be Warkitu, a mutant Lakitu. Mario got into his usual stance to take down this "Warkitu". However, Warkitu started to throw more Bob-ombs on the ground. Peach ran behind Luigi for safety while Mario tried to dodge the bombs, but Mario was hit and knocked out cold...

When he finally came to, he found himself in an odd world. Fortunately, Toad found him just in time to explain what was going on. Toad told that Bowser had stolen a powerful crystal that magnify the natural forces of the world. Everything had mutated. Some of Mario's enemies had become more powerful! However, Mario's abilities also became more powerful! Toad explained that the crystal's power worked for both good and evil. Mario obtained a nearby Fire Flower that changed his clothes to an unfamiliar orange. Mario found himself jumping higher than before, and his fireballs moved in a straight line! When they came in contact with an object, they didn't disperse, they continued going! Mario smiled and knew that with these new powers, he must set out on another adventure in this strange new land to restore peace and find out what happened to Peach and Luigi!

Mario traveled to the usual place that lead to Bowser's world, but the entrance was gone! Not knowing what to do, he asked Toad what could done. Toad explained that the only way to reach Bowser's Castle is by warping there. So Mario journeyed to the Warp Zone. On his arrival, he saw there were giant locks blocking the path to the warp pipe to Bowser's world. He asked a local who had put them there. The local explained that Bowser placed the locks there and hid the magic keys to them in the seven worlds that can be visited from the Warp Zone. Mario thought, no sweat, he would just go find the magic keys and unlock the locks. However, little did he know, Bowser had hidden the keys very well and guarded many areas to throw Mario off. And to make it worse, each of his kids had re-stolen the wands, which would be needed if Mario were to activate the magic needed for the keys to work. A very complex situation laid before Mario. He knew he had to do it. So packing a bag for collecting coins, Mario set off on his adventure...