The movie begins with Endsville, two weeks from the past as an Underworld Master; the Lord of Horror sends Billybot and Mandroid, two unrealistic robot replicas of Billy and Mandy, to the past to stop Mandy and Billy from obtaining Horror's Hand, a giant gauntlet which the Lord of Horror has himself. As Mandroid and Billybot leave in a giant swirling vortex, future Billy and Irwin remember the old times and discover themselves too late to go in the vortex with Mandroid and Billybot. Billy takes out his blueprints for a new time machine but turns out that it's merely a drawing of policemen fighting dinosaurs (Billy states they should be working together). The duo decides to make a time machine while the audience must guess where Mandy or Grim is in the future.
Meanwhile, in the past, Grim goes to reap General Skarr, who first thinks Grim is the TV repairman. He discovers the truth when Grim sends the TV into a vortex. It turns out that somehow Skarr has a hole through his stomach. Grim discovers Billy and Mandy in the room as well. Mandy claims that the two are bored and want to go with Grim to work. Grim refuses and Mandy claims that since Mandy won Grim in the game of Limbo, Grim has to be their best friend, and any best friend would take they're other friend to work if the friend had a cool job. Skarr makes a run for it in a modified car and Grim and the children chase Skarr using Grim's scythe as part broom and part car. While Grim argues with the children, they crash into a gas station, causing a petrol meter to fall on Billy's head. They then crash into a fireworks tent having fire crackers in their clothes and mouths. They also end up turning over an oil truck. Later, Skarr even uses oil slick which merely causes the scythe to scrape the ground igniting a fire starting in the oil and following the group. Skarr then sends a heat-seeking missile at them. Skarr finally moves into the ocean by turning his car into a sub and happy that he cheated Death. Skarr notices a button and pushes it. He realizes that the button shot a laser through his stomach making the hole again (the first hole must've healed). The group discovers the oil truck behind them and the small fire coming. When the fire hit the oil truck, everything exploded in a result with addition to the fireworks, all in an apocalyptic manner. The angry group comes home to Billy's house, burnt. Irwin comes in dressed in a bear suit trying to woo Mandy but fails. Mandy slams the door on him and is surprised when Irwin is sitting on the couch. Suddenly, the Underworld police break in and send Grim to court.
In court, Grim discovers that he's charged for abusing his powers. The jury is split up in pairs and each pair sits atop a giant pillar that looks like a gorilla arm. The jury includes Dracula, Bride of Frankenstein, Wolfman, Fred Fredburger, the blue juror annoyed by Fred, a mud ghoul, Darth Vader, The Invisible Man, and about two other citizens. The fly guard is also seen. Of course, Judge Roy Spleen is judge as he sits in the flaming mouth of a giant statue head. To everybody's surprise, the Boogeyman is the prosecutor. In the end, Fred Fredburger finds Grim and the gang innocent. But later, the blue juror states that the paper reads guilty. Boogey has the kids and Grim in custody onboard the Boogey Bay and Numbuh 3 (guest starring as an evil being trying to reap parents from the KND) becomes the new reaper. Boogey states that she's on a six-week trial period. Along with a few supernatural pirates and Boogey as captain with his first mate, Mr. Creeper.
Meanwhile, Billybot and Mandroid go to Billy's house where they attempt to get information out of Billy's dad. The androids find nothing and Billybot gets damaged after drinking root beer and malfunctioning, making Billybot's head fly off, after which he lights on fire. Boogey's ship makes it's way to the Dead Sea, where Boogey plans to feed the gang to Lava Sharks. Boogey reveals his plot to steal Horror's Hand and use it to be scary again. Then he'll scare every kid in the world through their dreams, and all would vomit at the mere mention of the name "Boogeyman". But first, Boogeyman must conquer his worst fears to own the Hand. Boogey sends Billy first to walk the plank. Billy reveals that he's not scared as long as the sharks don't eat him and starts singing. Along with the song, Mandy and the rest of the captives make a run for it. Billy sings the song about how he's not scared of anything and at the end of the song, he briefly sings about how he's hungry. Irwin, Mandy, and Grim make a run on the deathboat (reverse lifeboat). Billy comes along and Mandy asks what he was doing, Billy responds saying that every animated movie has songs. Mandy sees Boogey dancing and claims that that's scary.
Boogey is first to go through the gate to Horror's Hand and claims that Billy and Mandy must go through the Gatekeeper to go through the gate, so Boogey uses The Gatekeeper's Magic Eye to witness the team's demise. The group sets out to stop Boogey and claim Horror's Hand. Mandy wants to rule the world with the hand, Irwin wants to woo Mandy with the hand, Billy wants to buy a candy bar, and Grim could reclaim his role as Grim Reaper and get his scythe back. The group meets a blind cyclops with an eye-patch. The cyclops sends the gatekeeper, a giant orange cyclops, to go test the children. The gatekeeper demands they bring their greatest riddler. Irwin offers to step up, and the gatekeeper smashes Irwin with his club. The test is actually a taste test as the gatekeeper puts the group in his mouth to see if they taste good. The group has passed the test. The gatekeeper puts the group into a soup to wait for them to cook. Mandy fakes the cyclops into thinking Billy urinated/farted in the soup. Billy reveals he actually did and the gatekeeper throws the group out. Mandy jumps out and steals the gatekeeper's eye. There is a fight and as the gatekeeper pushes Grim to the ground, Irwin attempts to grab the eye, but then it falls on his head, then he throws it to Billy and the eye ends up eaten by Billy. Boogey turns his head in disgust as he looks where the eye goes. Creeper offers to build the Billybot and Mandroid and shows Boogey the blueprints. Suddenly, Billybot and Mandroid teleport into the ship and Boogey states Creeper worked fast. Mandroid offers to help Boogey and Creeper destroy Billy and Mandy.
The group run away from the Cyclopses' Cove and discover a giant cake as they run near the getaway ship. Mandy is suspicious but a crazy Irwin and Billy stuff the cake into Mandy and Grim's mouths. Suddenly, the rest of the group fall into a sleep and Mandy soon follows into the trance. Mandroid comes out of the cake and reveals that Billybot laced the cake with sleeping potion. Of course, due to his newfound stupidity, Billybot eats the cake and states "he is dreaming he is a pygmy marmoset". Now asleep, the team is vulnerable to dream infiltration by Boogey. The group has a hive mind dream, where Billy dreams he is the world's fastest cowboy/astronaut, Mandy and Irwin relive "The Pit and the Pendelum" (Mandy having Irwin strapped to a table, laying under a pendelum) for the thousandth time, and Grim dreaming about being mayor of Puppytown. Billy is confused about who's the real Grim, the fancy-dressed Grim or the horse Grim from Billy's dream. The fancy-dressed Grim states he's the real Grim, and the horse Grim from Billy's dreams is just some guy from his sick, twisted imagination. The horse Grim reveal to be Numbuh 3 on charity work for "The Stupid Kids' Dream Foundation". Then Boogey comes and kidnaps Mandy, and farts in Grim's face. Boogey snaps his fingers and causes the ground to disappear, after which Billy states he usually doesn't wake until he wets himself. Irwin begs him to do so, after which everyone wakes up.
Meanwhile, on the Boogey Bay, Mandy is tied to the figurehead and Boogey says that with Horror's Hand, he'll be twice as scary as Grim ever was, and that Mandy can be his friend. Mandy states that just because she's friends with Grim doesn't mean she'd be friends with a guy like Boogey and that she'll hurt him so bad, he'll have to sit on his eyes. Boogey states if she's kicking any butt, she's dreaming. First, she wakes up in her room, then she opens the door and sees a stormy desert. Then, she wakes up with Billy, Irwin, and Grim, then Billy asks was she having that dream about when she can't save them, and the camera pans to show a hideous amalgamation of Billy, Irwin, and Grim. Then, Mandy wakes up in a room surrounded by Irwin-sounding stuffed unicorns, saying without Mandy, they're doomed. Last, Mandy wakes up in an inescapable black void. Boogey laughs as a mad Irwin storms in and beats up all the pirates. Grim tells Billy that love makes people do stupid things. Billy reveals that he loves everything and Grim says that, that explains a whole lot (why Billy is stupid). Irwin kisses Mandy, who awakes to Grim's and Billy's utter disgust. Mandy is grossed out. Mandroid comes in and threatens them with a laser gun. Mandy is disgusted by how unrealistic Mandroid is, stating she does not take orders, she does not "assimilate" , and she does not listen to Mandroid's pathetic excuse for a Boogeyman, and causes Mandroid to malfunction. Mandy takes the laser gun and shoots a stalactite down, stopping the pirates from attacking and the group makes a run for it on the deathboat and goes in the lead to the Island of Peril--resting place of Horror's Hand. Boogey sends the Kraken to go after the four. The group climbs up the long stairs of the temple and meet Horror the Ancient and his severed left hand at the top of the temple. Horror states that he channeled all his fears into his left hand and cut it off in order to become courageous. But new fears came so now, He said he now just plays on his computer, and learned how to play a guitar with his teeth. Boogey comes in and the Kraken engulfs Billy to everybody's horror. Horror states in order fot two parties to compete for the hand, they must hold the Cannibal Run and the winner will have to fight Horror and then receive the hand.
Boogey's ship gets a sea monster tied to the ship for extra speed, and Mandy, Grim and Irwin must race in their deathboat without Billy. Mandy shows a sign of weakness before Billy resurfaces and reveals he lived by breathing his own farts and also made friends with the Kraken. The race starts and the team go through the Glacier of
Doom, which grows a face, and Mandy destroys the glacier with the laser rifle. They enter the Hole of Oddities, where they become live-action puppets. The go to the Sunken City of the Sea Witch and destroy the sea witch by using Irwin's glasses to redirect her magic laser to turn her into a frog, and Irwin ends up getting a frog head. They go to the Picnic Grounds of Terror, and go through the Corridor of Blades. Their deathboat is chopped up and they glue back the ship with Billy's snot. After all that, the heroes win and easily defeat Horror by Mandy taking Billy's nose and throwing it at Horror. The group tries to face their worse fears--Billy's fears of spiders, clowns, and the mailman, Irwin's fear of telling jokes to wild bears and accidentally insulting them, and Mandy's fear of growing up to lose her evil ways and marrying Irwin. But Grim is the only one who conquers them as he lives his worst nightmare every day; living with Billy and Mandy. But Boogey steals the hand and uses it to "scare Grim to pieces". But Boogey is defeated by his worse fear: discovering that he's not scary. Grim later reveals that he turned the Hand off and Boogey now is living his life in his fears forever. The police and Judge Roy Spleen come in. But Mandy convinces or threatens the judge, so Judge Spleen decides to offer Grim's job back with Numbuh 3 fired. Judge Spleen states that she was a heck of a reaper in her own way. Grim decides to put the Hand in his trunk. Irwin states now he can use the hand to make a certain someone like him, and Billy can scare people into thinking he's smart. They then start fighting over the Hand. The team learns a valuable lesson when Fred Fredburger says the nachos he ate hurt his stomach, yet if he didn't eat them, he would've never known he could finish them all. Grim saved the world even without the scythe, Mandy is still mean and demanding even without the Hand, Irwin finally got to kiss Mandy, and Billy is getting a new bike for Christmas. Mandy then hides the hand behind her back. To everybody's surprise, future Billy teleports in the temple and reveals that Mandy is planning to rob the Hand. Mandy merely shrugs and hands the hand back to Grim. The group returns home with Future Billy saying his farewell. Billy asks what he's going to have for lunch next Tuesday and Future Billy replies, "I could tell you, but then I would have to kill you". The Future Billy explodes into the future, burning off Billy's face with Billy replying "I like that guy". Mandy orders Grim to make them hotdogs. Meanwhile, Billybot and now more realistic Mandroid order Creeper to serve Billybot's drink. Billybot drinks the root beer and his head explodes again.
After the credits, future Billy goes back to his own time to discover that nothing has changed and someone has stole the hand out of Grim's trunk and the Lord of Horror is now Fred Fredburger.