Mario, Luigi, Toad, and Princess Toadstool travel to Sockhop Land in search of the music king Elvin Parsley. They first ask a Toad where to find Elvin. The Toad gives a response heavily steeped in 50's slang that Mario and the others cannot understand. Suddenly, every Toad in the town starts to get scared. As Mario and the others turn around, they see the Goomba Biker Gang with King Koopa in a red convertible following behind. Every Toad then runs for cover. The Goombas and King Koopa stop in front of Elvin's recording studio and replace his picture on a billboard with King Koopa's picture that says, "King Koopa, King of Sock Hop Land". Koopa then sees Princess Toadstool and goes after her. Mario grabs the Princess and runs with Luigi and Toad into an alley. They find a dumpster and pushes it into the Goombas and King Koopa pursuing them.
Mario and the others walk into a neighborhood and find Elvin's mansion, Parsley Land. As they enter the mansion, they hear the song "Jailhouse Rock" play. They also hear a sound coming from a closet. In it they find Elvin's boots that talk.
The boots lead Mario and the others to King Koopa's hideout, the Half Life Malt Shop. As Mario and Luigi peek inside, they see many Goombas seated at tables with a stage at the back. Mario, Luigi, and Toad sneak onto the stage and play music to distract the Goombas while Princess Toadstool and Elvin's boots go to find Elvin Parsley. They find him in a freezer, frozen solid. Before the Princess could put the boots back onto Elvin's feet, King Koopa kidnaps her. As Mario, Luigi, and Toad play, King Koopa grabs Toad. Mario then starts a food fight to distract King Koopa and saves Toad. They run out of the malt shop, food still flying everywhere. Koopa comes after them, but he slips on a banana.
Later, King Koopa, with Princess Toadstool, drives his red convertible into town to show off. He drives past an alley where Mario, Luigi, Toad, and Elvin's boots are hiding. After a long time of thinking up a plan, Mario finally says that they should make a hot rod of their own to go after Koopa. They find an old truck and start fixing it. Luigi took the job of pumping up a tire. The tire then got too big and blew up, transforming the truck into a hot rod.
Mario and the others caught up with King Koopa and drove in circles around him. Luigi grabbed the Princess and they drove off. Mario then saw the Goomba Biker Gang charging toward them. One of them then kicks a Bob-Omb at them and blows up a tire, spinning them out of control. The car crashes and blows up into many pieces. Mario and Luigi find a field of Fire Flowers and they turn themselves into Fire Mario and Fire Luigi. They attack the Goombas with fire balls making the them run away. Then Mario and Luigi go after King Koopa and drive his car off a cliff.
With Koopa gone, Mario and the others go back to the malt shop and free Elvin Parsley. Mario and Luigi go outside to tell everyone that the king is back. The Toads come out of their hiding places and come to hear Elvin sing. Mario asks if he could play with Elvin. Knowing that Mario plays horribly, Luigi, Toad, and Princess Toadstool yell, "NO!", much to Mario's dismay.
Animation and continuity errors