Mario and his friends have traveled to Crime Land during the midst of the city's worst crime wave ever, which has been caused by King Koopa, who is now going by the alter ego of Al Koopone. Stepping out of a taxi, Princess Toadstool questions as to why the city is called Crime Land, due to the lack of action. At that moment, they notice Mouser, Koopa Troopa and Tryclyde, now wearing business suits and fedoras, exiting a bank with sacks of money and violin cases.
Mario suggests that they should stop the Koopa Pack, and chase the criminals back to their car. Mario threatens the Koopa Pack by announcing a citizen's arrest, but they instead reveal the Snifits hiding inside their suitcases, which fire bullets at Mario's group. Mario's group manages to dodge the bullets by ducking, although the Koopa Pack eventually retreats into their car and drive off. Princess Toadstool then comments that she's certain that the crooks are obviously working for Al Koopone. Mario then decides that they need to teach Al Koopone that crime does not pay.
Meanwhile, at a soda bar called the Koopa Klub, Al Koopone comments that the place is perfect for his new headquarters. Sitting at the desk in his office with his feet raised, Al Koopone content that Mario's group won't be able to get inside. The Koopa Pack then enters Al Koopone's office, carrying several stacks of pink boxes. Tryclyde informs Al Koopone that the boxes are his latest order from the Gangster Supply Store, much to his delight. Al Koopone orders his henchmen to place the boxes down, but they all stumble over and fall, revealing the hats that had been inside them. Koopa Troopa isn't very impressed by the hats, but Al Koopone informs him that they are magical, and orders the Koopa Pack to wear them. Al Koopone then pulls a Snifit out of his violin case and fires at the frightened Koopa Pack, only for the bullets to ricochet off of them unscathed. Al Koopone laughs that his new hats work, as they make the wearer invulnerable to any attack. He then tells the Koopa Pack to get ready for an upcoming Koopa caper.
Back on the streets of Crime Land, Mario reads on a wanted poster that Al Koopone is public enemy number one. Princess Toadstool mentions that if they ever hope to catch him, they'll need to know what his next caper will be, but Toad comments that nobody in town will tell them, as they are all to scared to squeal on Al Koopone. Mario claims that they need a stool pigeon, and is called over by a voice from a nearby alley. Luigi points out that they've been called by a Stool Pigeon, and they all run over to him. The Stool Pigeon agrees to tell the group what the caper will be, provided they pay him. Toad pulls out a bag of chicken feed, prompting the Stool Pigeon to reveal that Al Koopone will be robbing the First Mushroom Bank.
At the First Mushroom Bank, Al Koopone and the Koopa Pack barge in through the front door, threatening to shoot all the Mushroon People inside with Snifits. After Mouser intimidates the citizens, he notices the bank's vault. Al Koopone pulls out a Bob-Omb and bowls it down towards the vault door, blasting it open, and sending the Gold Coins within flying across the room. Before the Koopas can react, Mario's group exits from the vault, startling them. Al Koopone asks Mario's group to do their worst, prompting them to toss Vegetables at the Koopas. When the Vegetables all bounce off the Koopas due to their Unzappable Hats, Mario attempts to attack Al Koopone with his plunger, but instead gets thrown back by the power of the hat. Al Koopone then orders Mario's group to raise their hands in the air, and upon being asked by Mouser as to what they should do with their hostages, tells Mouser to take them for a ride.
Some time later, now atop bridge over a river, Al Koopone and the Koopa Pack stand before Mario's group, who have been fitted in cement shoes and tied up in rope. Princess Toadstool demands to be freed, but Al Koopone mocks her plea. Toad comments that his cement shoes are hard to walk in, and asks for someone to take his off. Koopa Troopa offers to help, but Al Koopone angrily grabs him, stating that Mario's group is supposed to drown in the cement shoes, not walk in them. With that, Al Koopone kicks Koopa Troopa and sends him flying across the city. Al Koopone then pulls a lever, opening a trapdoor in the bridge that Mario's group falls through.
Mario's group sinks to the bottom of the river, where Luigi complains to Mario that he's gotten them into yet another fine mess. Mario then notices a glimmer and directs his friends' attention over to a nearby Starman lying on the floor of the river. Mario forces himself to fall down face first next to the Starman, and manages to grab it with his mouth. Using the Starman's power, Mario powers up into Super Mario and manages to burst out of his cement shoes and rope. Taking on the pose of a baseball pitcher, Mario simultaneously tosses three fireballs at the cement shoes of his friends, freeing them. Luigi, Princess Toadstool and Toad then manage to untangle themselves from their ropes, just as Super Mario's power's wear off. Princess Toadstool then demands to her friends that they get back at Al Koopone and they all swim up to the surface.
Mario's group later arrives outside the Koopa Klub, where Mario announces that he will get them all inside the place. Mario, Luigi and Toad, dressed as gangsters, along Princess Toadstool, dressed like a showgirl, approach the front door of the Koopa Klub and knock. Opening a lookout window, Mouser asks the group for their identity. In a scratchy voice, Mario tells Mouser that they are Aface and his gang. Mouser then asks them for the password, but none of them know what it is. Fed up with their slow response, Mouser shouts that it is "cheese balls". Using this information, Mario tells Mouser the password, and he foolishly allows them to enter the Koopa Klub.
Inside the Koopa Klub, Mario and his friends take a look around. A Koopa Troopa is serving three drinks to Tryclyde at the soda bar, while an Ostro and Birdo couple dance to music played by a Shyguy on double bass, Goomba on piano and Pidgit on saxophone. After Toad admires the place, Mario comments that they need to find out where the Unzappable Hats are being held. Princess Toadstool then notices the coat check room and suggests that they check it out. Mario's group then sneak into the coat check room and take out the Koopa Troopa that's guarding the place. Removing their disguises, Mario and his friends each don an Unzappable Hat and prepare to face Al Koopone.
Sitting at a table, Al Koopone asks himself the question "Who says Koopa Crime Doesn't Pay?". Mario answers the question by saying that his group does, much to Al Koopone's annoyance. Al Koopone then orders the Koopa Pack to attack them with their Snifits, but the bullets do no damage whatsoever. Mario and his friends then toss several Vegetables against the crossfire of the bullets at the Koopas, causing Al Koopone to hide behind a turned table and cower. The Vegetables eventually hit Mouser, Koopa Troopa and Tryclyde, knocking them all aside. Princess Toadstool then grabs the soda sprayer from the soda bar and uses it to blast away the band. Al Koopone tries to make a break for the exit, but Mario jumps in front of him, telling him to give up. Al Koopone then pulls out a Magical Potion and tosses it, creating a door which he enters to escape from the Koopa Klub via a Warp Zone. Luigi is mad that Al Koopone got away, but Mario points out that at least he's finally gone from Crime Land.
Having taken off their Unzappable Hats, Luigi, Princess Toadstool and Toad exit the Koopa Klub, and fret over the fact that they've been unable to find Mario. From atop a ladder, Mario calls down to his friends and announces that he's changing the name of the Koopa Klub since they've chased Al Koopone from Crime Land. Luigi, Princess Toadstool and Toad ask what the new name is, and climbing down the ladder, Mario turns on the new sign he set up, revealing that the new name is Mario's Pasta Palace. Mario then mentions that up until this point that Crime Land didn't have a single Italian restaurant, which in his belief, really was a crime.
Animation and continuity errors