Kootie Pie is applying makeup when she hears King Koopa coming to see if her room is clean. She hides the mess in her wardrobe, but Koopa is not fooled and he grounds her, which infuriates her. Kootie Pie complains about having a rotten father, and just as Big Mouth intrudes, Kootie Pie figures that Koopa must not be her real father. The two also decide that their father must be someone magnificent, like a movie star.
Meanwhile, Mario and Toad are searching for a Fire Flower when the Doomship collides with them. Mario and Toad tumble right into a patch of Fire Flowers, but soon notice the Doomship. It is revealed that the two Koopalings are trying to pilot it (which is why they crashed into Mario) and arguing over which way leads to Hollywood. The Doomship flies into a Warp Pipe, but not before ripping the roof off of Toad's house. Luigi and Princess Toadstool run out and Mario explains what happens. The group decides they must follow the Koopas.
In Hollywood, Kootie Pie and Big Mouth find themselves amongst the Walk of Fame, when a giant reptilian monster named Madzilla appears from behind a building. They decide that the monster must be their true father, only to see a film director turn the monster off with a remote control. Still believing Madzilla is their father, the two try to help Madzilla with their magic scepters. Once he wakes up, he scares off the confused director and places the Koopalings on top of a building. Big Mouth explains how Madzilla put them up for adoption (or at least their beliefs thereof) and they request Madzilla get them a convertible. Instantly, Madzilla takes a car off the road, rips off the roof, places the "convertible" on the roof, and sticks the two Koopalings in it. However, they tell him it's not good enough, and so begins their long line of demands from him.
Meanwhile in a separate area of Hollywood, Mario, Luigi, Toad, and the Princess pop out of a Warp Pipe in a sewage area. Mario tells the gang to follow him until they see Dadzilla storming through the city. Kootie and Big Mouth then catch Mario out of the corner out of their eye, and Kootie Pie tells them about how they did "terrible things to [them]". Madzilla grabs Mario by his overalls, when Mario remembers his Fire Flower. He burns Madzilla's hand and gets ready to fight him, when Kootie Pie decides that Madzilla needs help and wears Mario's powers away with her scepter. The gang is chased by Madzilla into a props garage, but the Koopalings announce bigger things to attend to: their becoming of movie stars.
While Kootie Pie, Big Mouth, and Madzilla put their feet in the cement in the Walk of Fame, Mario explains an idea of his to the gang. He points out a large head that greatly resembles Madzilla - or at least a female version of him. Luigi recognizes it from the monster movie "Revenge of Madzilla's Mom". Mario then tells them that they can rebuild Madzilla's Mom to counter the Koopas.
Madzilla tries to catch up on his rest when Big Mouth and Kootie Pie tell him they want to perform a live concert for everybody in the Hollywood Bowl immediately. Somewhat annoyed, Madzilla heads for the Hollywood Bowl, pulls it out of the ground, and places it over Big Mouth and Kootie Pie. They then begin playing "Stomp My Name on the Walk of Fame". The audience hates it and throws assorted objects at them, like catapulting various items off of a palm tree, and then throwing the palm tree at them. The Koopalings manage to dodge most of the items thrown at them until the end of their performance, at which point they are both hit.
Back in the props garage, Mario activates Madzilla's Mom, which is crudely built out of several monster body parts. It takes off to find Madzilla, as the gang watches. The Koopalings are now buried in garbage thrown at them. Kootie Pie crawls out and screams at Madzilla. He tries to cheer for them, and the audience directs their garbage at him. He attacks the audience for not cheering, when his "mother" appears. She (really Mario) tells Madzilla to put the people down, when Kootie Pie objects, telling him he's only supposed to obey them. Madzilla's Mom looks down at the two Koopalings, then tells them it's time for their nap, and then, chores. The Koopalings think about how their life back home was much better, and retreat back to Dark Land.
Mario (still in Momma Madzilla) leads Dadzilla to the now destroyed props garage, and explains how he was once a robot. The Princess tells him that he will be free to live in Giant Land, and, best of all, he won't have any kids to deal with.
Animation and continuity errors
Names in other languages