At long last, Mario and his friends have finally driven King Koopa and his evil minions out of the Mushroom Kingdom. The citizens are now free, and Princess Toadstool can now reign in her castle again. For their deeds, the Mushroomers even throw a parade for Mario's group. Having saved the kingdom, Mario and Luigi are now ready finally return to Brooklyn.
Arriving at a newly-discovered Warp Pipe, Princess Toadstool gives Mario and Luigi each a kiss, announcing that she's going to miss having them around, and begins to cry. Mario assures her that she needn't worry, as he and Luigi can travel through the pipe to come and visit any time they want. Luigi then tells Mario that not having to deal with King Koopa any more will make their lives perfect as pasta. The thought of pasta reminds Mario of their mother's cooking, which prompts him to leap into the pipe, as Luigi follows and the Mushroom People bid them farewell.
The pipe warps Mario and Luigi into a Brooklyn sewer, where they emerge from a manhole. Back in Brooklyn, Mario and Luigi begin to admire the many local sights, including the tree that grows in Brooklyn and the Brooklyn Bridge. Mario then points to the Statue of Liberty, but is baffled to see that it has taken on the appearance of King Koopa, which he dubs the "Statue of Kooperty".
Mario and Luigi turn around when they hear someone scolding a crook, and see a policeman chasing a Koopa Troopa who's holding a sack of money. The Koopa Troopa storms past Mario and Luigi, who are surprised to see it in Brooklyn. A second Koopa Troopa then sticks his leg out from behind the garbage can, causing the policeman to trip, and the two Koopa Troopas run off with the sack of money. Mario then concludes that King Koopa and his minions have undoubtedly invaded Brooklyn, and Luigi notes that King Koopa merely left the Mushroom Kingdom so that he could take over their hometown. Mario tells Luigi that they need to find and stop King Koopa, so they hail a taxi and tell the driver to follow the Koopa Troopas.
The taxi brings Mario and Luigi to Coney Island, where numerous Koopa Troopas are hanging out and riding on the rides. The cabbies then questions as to what an ugly, fat, reptile is doing with the Coney Island entrance sign, and Mario points out that it's King Koopa, who's replacing the sign with one that reads "Koopa Island". The cabbie then yells at King Koopa, and tells him to leave, but gets ignored. Mario then worries that King Koopa will change Brooklyn to Kooplyn, but Luigi assures him that not even King Koopa would be that mean. At that moment, they overhear King Koopa telling the Koopa Troopas to replace every sign that reads Brooklyn to Kooplyn. King Koopa then announces that once the signs have been changed, they'll cross the Kooplyn Bridge, capture the rest of New York and make it "New Koopa".
Fed up with King Koopa's tyranny, the cabbie announces that he's going to find the police, but attracts the attention of King Koopa, who sees that Mario and Luigi have finally arrived, just as he planned. King Koopa orders his Koopa Troopas to capture the Mario Bros. for him, and they begin to give chase. The cabbie begins to leave, but assures Mario and Luigi that he'll be back with the police in three minutes, and that he expects a triple tip. As he drives off, King Koopa uses his Koopa scepter to transform the cabbie, as well his entire taxi, into a pile of bricks. Luigi begins to worry, because he figures that King Koopa has the power to turn everyone in Brooklyn into bricks. King Koopa announces that it's his intention, as he wants vengeance on Mario and Luigi for foiling his evil schemes in the past, and has decided to take it out on their hometown.
King Koopa orders his Koopa Troopas to attack Mario and Luigi. Mario manages to bounce on several of their heads, and leaps onto the nearby roller coaster track, where he kicks a Koopa Troopa out of a car. Luigi then follows Mario's moves, and boards the car as well. While they ride along track, King Koopa uses a walkie-talkie to alert his minions that Mario and Luigi are riding on the roller coaster, and gives the order to attack. Luigi then questions if they're on a one-way roller coaster, as he points to a car full of spear-wielding Koopa Troopas, equipped with a plow, heading towards them in the opposite direction. Mario tells Luigi to hit the brakes, but he retorts that there aren't any. Mario then suggests switching to reverse gear, but that isn't an option either, so he tells Luigi to bail out. They jump out of the car right before it collides with the other one, and proceed to run down the track in the other direction, now being chased by the Koopa Troopas. Watching from the sidewalk, King Koopa points out that the Mario Bros. have finally made it back to Brooklyn, just in time for their own funerals, and laughs.
Luigi then tells Mario that if he'd known how scary Brooklyn would've been, he'd have stayed with Princess Toadstool and Toad. Mario then reminds Luigi that at least they're safe in Mushroom Land. Back in the Mushroom Kingdom, Princess Toadstool and Toad are sitting down to a nice, relaxing picnic lunch, where they acknowledge the peaceful state that the kingdom is now in without the Koopas around. However, the two of them are currently bored, and note that they do miss Mario and Luigi. Princess Toadstool suggests that they should pay them a visit, as she's always wanted to see the so-called "Brooklyn Kingdom", and they leap into the pipe.
Meanwhile, Mario and Luigi are still being chased down the roller coaster, when they see King Koopa and several more Koopa Troopas standing on the track up ahead, leaving the brothers between a rock and a hard place, with no real options. At that moment a garbage truck, driven by Princess Toadstool, comes speeding into the park and crashes into a support column of the roller coaster, the impact of which causes the track to separate. The Mario Bros fall through the gap and onto the garbage truck, while the Koopa Troopas crash into Lower New York Bay. As King Koopa and the other Koopa Troopas look down to see what happened, Toad tells Princess Toadstool to floor it against the column, which knocks King Koopa and the Koopa Troopas onto the horses of a carousel.
Mario and Luigi emerge from the garbage into the truck, and Toad apologizes, stating that the garbage truck was the only thing they could find to rescue them in time. Mario questions why they're in Brooklyn, and Princess Toadstool tells them that their lives are no longer the same without him and Luigi around. Mario then advises them to return to the Mushroom Kingdom, and things could get really bad with King Koopa around. However, Princess Toadstool refuses to leave, stating that she and Toad owe it to them to save their homeland from King Koopa after they saved the Mushroom Kingdom. King Koopa then mocks her from atop the carousel, stating that both she and Brooklyn have seen their last days, which strikes fear into Luigi.
Now at the Brooklyn Bridge, King Koopa announces his new plan to his minions. First off, the Bob-Ombs are to blow up the Brooklyn Bridge, to which the minions cheer, as he assures them that the Princess and Mario Bros. won't be able to follow them if the bridge is out, and that they can take step two, which a Koopa Troopa notes would be to turn all the people of Brooklyn into bricks. Another Koopa Troopa asks what they'll do next, and King Koopa states that he'll crown himself the King of Kooplyn, and make all the laws, which include: No plumbers. No pasta. No princesses. Brooklyn accents are not allowed. Hearing this, the minions cheer some more.
Eavesdropping from inside some nearby garbage cans, Princess Toadstool notes that they were fortunate enough to find King Koopa before he could get away with his plan. Mario assures her that King Koopa won't get away with anything, and tells Luigi to follow him as he runs off, while Princess Toadstool and Toad hide. Meanwhile, the Koopas start to toss several Bob-Ombs off of the bridge, and manage to blow up a portion of one of the bridge's bases, which causes two support cables to snap.
Suddenly, several police officers come running onto the bridge, but King Koopa stops them in their tracks by turning them all into bricks. The Koopa Troopas then toss these bricks at Mario and Luigi, who stuggle to catch them all, as they don't want them to break. King Koopa then places his Koopa Scepter down to pick up an antsy Bob-Omb, but Toad uses the opportunity to swoop in and grab the Koopa Scepter, which he runs off with. Toad passes the Koopa Scepter to Princess Toadstool, who uses it to restore all the bricks back into police officers, who chase after the Koopa Troopas. King Koopa then lights the Bob-Omb's fuse, and tosses it at the police, but Mario intercepts by catching it. Mario then tells his friends that the only way they can save Brooklyn is by luring King Koopa back to the Mushroom Kingdom.
Toad tells King Koopa that if he wants his scepter back, he'll have to come and get it, and runs off with his friends. Outraged, King Koopa gives chase, and follows Mario's group through the streets of Brooklyn. Meanwhile, Luigi warns Mario to drop the detonated Bob-Omb, but Mario explains that it's not time, just as the group leaps into the manhole back to the Mushroom Kingdom. Emerging from the pipe in the Mushroom Kingdom, Luigi again tell Mario to let go of the Bob-Omb, but he still insists on waiting. Once King Koopa comes through the pipe, Mario tosses the Bob-Omb into it, causing the pipe, along with the only way back to Brooklyn to blow up.
King Koopa asks why Mario blew up the pipe, and he responds by saying that he's stuck in the Mushroom Kingdom, and that Brooklyn is now safe. Mario's friends applaud him, but King Koopa reminds Mario that he's still stuck with him, and proceeds to swipe his scepter out of Toad's hand. Now frightened, Mario and his friends begin to run off, while King Koopa attempts to zap them with his scepter. While running from King Koopa, Mario mentions that someday, even Super Mario can't think of everything.
Animation and continuity errors