In Australia, A young boy named Cody rescues a golden eagle named Marahute, who is the last of her kind, is raising eggs, and had a mate that was killed. Marahute takes Cody for a ride. A while later, Cody falls into a trap. Then, suddenly, while a little mouse tries to help Cody out, a goanna lizard scares Cody. Then Scroop, Deadpool, Clayton, Blowhole, and Plankton arrive with a new member, the wanted poacher, Percival C. McLeach. His pet goanna lizard spots one of Marahute's feathers on his backpack. Percival them reveals that he and the Villains accompanying him had already killed Marahute's mate, and had part of it's corpse eaten by his other pet, the Anaconda that once belonged to Dark Cynder, to use it's pure blood to restore Lord Cobra's corpse form (The Black Cauldron) back into a more purier form than he was on Madagascar, or Camelot. They succeed on getting his blood, but they realized that they needed more blood. Then they decided to find the mother in order to complete their mission. They even had their own plans for her eggs. They throw Cody's backpack into a stream full of crocodiles to keep the Rangers off their trail, or more frankly, The Shell Lodge Squad, and they kidnap Cody to try to get close to Marahute. The little mouse then sends a message to the Marshall Islands, then to Hawaii, to LA, to Denver, to St.Louis, to Chicago, to Washington D.C., and finally to New York. And even better, that's where the Shell Lodge Squad are hanging out for a visit to RAS after their quest for Merlin leads them directly there.
The Lodgers were talking with each other in an empty room until there is an emergency situation. They hear about the kidnapping in Australia, and are sent to find Bernard and Bianca after the Chairman finds them missing. The Lodgers find the duo on a date. Bernard was planning all month to offer Bianca her marriage using a ring he recently bought. Before he could ask, the Lodgers talk to them. As Bernard drops the ring, and goes after it, the Lodge warns Bianca about the kidnapping, and Shifu goes to tell Bernard. He finds Bernard right after he gets the ring back. He tries to tell him, but Bernard shrugs him. He returns, and misinterprets Bianca's words about the mission for his marriage to her. The duo and the Lodge go to RAS where they accept the mission.
The Shell Lodgers, Bernard and Bianca make it to Albatross Air Service where Orville last helped them, but instead, they find his brother, Wilbur, singing and dancing to the radio. They try to get his attention, but the music is too loud for him to hear. So, Bernard turns off the radio. After trouble with interpretation, Wilbur offers to take them to Australia. And while Bernard and Bianca ride on Wilbur, the non-aerial members hop in the van, while the aerial members fly on their own.
The next morning, as Wilbur along with the two mice and the Shell Lodge Squad hitch a ride on a plane, they take off again when they make it to Sydney, Australia. Wilbur jumps, along with the aerial Lodgers. The Shell Lodge Van takes off with them. They request permission to land to a kangaroo rat named Jake, along with his friends Sparky the Fly, and Tavin Tanner the first ressurected Tasmanian Tiger, but they say the runway is too short for him. Wilbur persists, and Jake tries to make the landing grid bigger. They succeed, and Jake leads the 2 mice and the Shell Lodgers, while Wilbur has broken his back, and is taken to the hospital. Bernard starts to get worried when Jake starts to get attracted to Bianca. And another jealousy occurs from SpongeBob when Tavin gets attracted to Sandy. She and Kowalski are amazed at seeing Tavin as a long-extinct species, and learn about how he was created by a Tasmanian Tiger cloning lab, and winded up with Jake.
Meanwhile, at McLeach's hideout, The Villain Leaguers try to get Cody to tell them where Marahute is, but he never cracks. As they keep trying, The Shell Lodgers hang out at a river doing activities, while Bianca picks burrs off of Bernard, who had recently landed in a burr bush. As Bernard tries again to ask of Bianca's marrige, Jake bursts in and fights a snake, and uses it to ride on. The Lodgers, of course, accompany them, and the two jealousies still occur.
Back at McLeach's hideout, Cody is caged until he talks. Then he meets a lot more animals that McLeach has caught, including a frill-necked lizard in the same cage Cody's in named Frank. They manage to get the keys, but are stopped by Joanna and the Anaconda. Then the Frill neck decides to use his tail to pick the lock. Meanwhile, The 3 mice ride fireflies through the swamp and the other Shell Lodgers develop their own ways of traveling. Back at the hospital, Wilbur breaks his back again, curing him. Wilbur then looks for Bernard and Bianca and the Shell Lodgers. Elsewhere, the Australian Rangers had recently found Cody's backpack, and warn Cody's mother about the situation. Back at McLeach's hideout, McLeach is thinking of a way to get to Marahute and her eggs. While he tries to make something to eat, Joanna keeps taking his eggs, and manages to eat all of them, at the same time, amusing the Villains. Then when McLeach gets angry, it suddenly occurs to him. He realized the bird's eggs were the key to getting to the bird. Meanwhile, Frank manages to open the cage after a long while of picking the lock with his tail. When he manages to get the keys, Joanna and the Anaconda hear them, and are eventually beaten. Cody manages to get free, and tries to free the others, but McLeach and the Leaguers arrive and take him away.
Meanwhile, the Lodgers and the mice, kangaroo rat, and Tasmanian Tiger finally make it to McLeach's hideout. As Jake suggests they use 'Open Sesame', the door actually flies open. McLeach, and the Leaguers take Cody outside. The Lodge overhears the whole thing. McLeach lies to Cody about Marahute being shot down, and lets Cody go, hoping that if Cody went for the nest, then the League could follow him and capture the bird. Overhearing about them mentioning birds and eggs, they ask Jake for any intel on McLeach's history. He told them that for years McLeach had been poaching for a rare golden eagle, and that he actually caught one before. Shifu then realizes the League's plan to restore Lord Cobra into a very powerful form using Marahute. They hitch a ride on McLeach's vehicle, and follow the Villains.
At Marahute's nest, the three mice try to warn Cody that he has been followed; just as they do, McLeach arrives and captures Marahute, along with Cody, Jake, Bianca, Tavin, and the Shell Lodgers. McLeach and the Villains are surprised that they captured the Shell Lodgers snooping in their plans, and decide to keep them around for a while. Joanna tries to eat Marahute's eggs, but Bernard found the nest first and replaced the eggs with egg-shaped stones in order to protect them. Wilbur arrives at the nest, whereupon Bernard convinces him to sit on the eagle's eggs so that Bernard can go after McLeach. The Villain League takes Cody, Marahute, and the heroes to Crocodile Falls, where he ties Cody up and hangs him over a group of crocodiles and attempts to feed him to them, while Deadpool is glad that the Shell Lodgers will be watching the whole thing. But Bernard, riding a wild pig, which he had tamed using a horse whispering technique used by Jake earlier, follows and disables McLeach's vehicle, preventing the use of its crane to put Cody at risk. Tavin manages to pick the lock, and allow him, Jake, Bianca, and the Shell Lodgers to escape, and battle the Villains. McLeach then tries to shoot the rope holding Cody above the water. To save Cody, Bernard and Tavin trick Joanna into crashing into McLeach, sending them both into the water. The crocodiles chase McLeach, while behind them the damaged rope holding Cody breaks apart, sending him plunging into the water. Although McLeach manages to fight off the crocodiles, only Joanna reaches the shoreline while McLeach goes over an enormous waterfall and eventually falls to his death. Soon afterwards, Icky breaks the fourth wall by saying that he smells stock footage from previous movisodes coming on, and advises anyone watching the video to skip to either another part of the movisode or a later time on the video. What follows is the typical stock battles where Po defeats Scroop and Deadpool, Skipper defeats Blowhole, and SpongeBob defeats Plankton. However, The Anaconda attempts to strangle SpongeBob until Cynder turns into her Avatar form, and tells the Anaconda to go away. Joanna's fate is unknown.
Bernard dives into the water to save Cody, but fails. Sandy tries second, but Tavin couldn't allow Sandy to sacrifice herself because he still loves her, so he dives in with her, only to discover that he can't swim. Tavin drowns, and Sandy tries pulling Cody and Bernard to the surface, but she is failing. SpongeBob couldn't bear to watch this either, and decides to rescue Sandy by going after her. SpongeBob tries helping Sandy, but he fails as well, and was on the verge of dying. But luckily, Jake and Bianca free Marahute in time for her to save Cody, Bernard, SpongeBob, Sandy, and Tavin, sparing them McLeach's fate. SpongeBob performs CPR on Tavin, and apologizes to him for his jealousy over him and Sandy. He and Tavin admit their love for her, but Sandy, confused for a while, decides to call it off for now. Meanwhile, Bernard, desperate to avoid any further incidents, proposes to marry Bianca, who accepts eagerly while Jake salutes him with a newfound respect. All of them depart for Cody's home. Wilbur, whom they have neglected to relieve of his task, incubates the eggs until they hatch, much to his dismay.
After leaving Australia and saying their goodbyes to their new friends, the Lodge discovers that Marahute's nest reveals another clue to Merlin's location, and discover it to lead to a French kingdom in another world. So they turn on their thrusters, and take off.
- Wilbur: CANNONBAAAAAAAAAAAAAAAAAAAAALL!,
- Genie: GERONIMO! ARAPAHO! NAVAJO! Pocohontas!,
- Batty: TORRO, TORRO, TORRO, TORRO!
- Jake: (Playing Checkers with his fly friend, Sparky) Well, Sparky, you've had this coming for a long time. Now you'r gonna get it! (Gets a checkmate) HAH! (Fly spits, and gets 6 checkmates in a row) Ugh, wise fly! (Fly laughs)
- Tavin: Well, I'd say Check, mate! (Laughs) Oh, that never gets old!
- Wilbur: (On radio frequency) Lugwall Tower! Lugwall Tower, this is Albatross 13 requesting permission to land, over!
- Jake: Albatross? (Flips over checkers pad to a list of birds with pictures of them depicting size) Let's see, Finch, Wren...Alba--Albatorss! I-It's a jumbo! (On microphone) Negative, 13, you'll have to turn back, our runway's not long enough for a bird your size.
- Wilbur: Not long enough? Look, pal, I can land this thing in a dive!
- Bernard: Uh, Wilbur, If the runway isn't long enough, then--
- Wilbur: Listen, you can't let these winger-jockies push you around! Just leave it to me!
- Tavin: Oh, for God's sake, let me handle this! (In microphone) Did you hear us, bucko? The runway is too short for you, you got that? You're gonna crash if you do it, anyway.
- Wilbur: Oh, please, you sound like a Tasmanian Tiger who got put on steroids.
- Kowalski: Uh, Wilbur, Tasmanian Tigers are extinct! (Tavin thinks: Not anymore, that is.)
- Wilbur: Really? I didn't know that. But enough messing around, we need to land if you're gonna save that kid.
- Jake: I say again, mate, our runway is too short!
- Wilbur: And I say again, 'mate', I'm coming in!
- Tavin: Well, we gave it our best shot. It's their funeral. Does anyone have a church organ around here?
- Jake: Oh, shush, Tavin, you and Sparky gotta help me extend the runway!