While out flying in his trusty airplane, Bulldog, an engine goes out and he crashlands in the middle of a forest. Righting himself, Wario starts exploring the area, when he happens upon a mysterious music box in a cave. As he approaches, he is sucked into a magical world inside the box.
A mysterious figure awakens Wario and begs him to help. The monsters in this world have imprisoned him, and Wario must collect all of the treasure to free the helpless being if he ever wants to escape the music box. Wario agrees and sets off to loot this world.
Wario has to use his attacks and transformations (suffered by touching enemies) to find keys and treasure chests. There are four treasure chests in each stage, each holding an item of some kind that will either increase Wario's abilities (allowing him access to new areas of levels), changing existing levels in some way, or unlocking new levels. You may have to defeat boss characters to reach keys and chests on some levels.
Along the way you get help from a mysterious being who lives inside a cave. You do not know if he is friend or foe, but he says he can help you escape - giving you pointers along the way as to where you should go next.