The beginning opens up somewhere in the 1679's with two veggie pirate ships fighting. The prince, Alexander is captured by Robert the Terrible, his uncle. The other pirates search the ship for the princess, his litte sister, Eloise. They cannot find her hiding spot and leave. But Eloise sends a device called The Helpseeker to find heroes to save Alexander.
After the title scene, this film tranfers to the present where George (Pa Grape), Sedgewick (Mr. Lunt), and Elliot (Larry The Cucumber) are shown working at a dinner theater callled Pieces of Ate. It shows that Sedgewick is very lazy, Elliot is scared of everything, and Goerge doesn't have a backbone, or he does what everyone asks him to do. After the show while cleaning up, an old man tells them that an adventure awaits for them that the stage is set for the heroes at hand. They think it means if they all audition, they'll be in the show.
After their audition (in which they destroy half the restaurant) they are thrown onto the streets, they then find the helpseeker and are sent back to the 1700s. They meet Eloise and her butler Willory (Archibald Asparagus). They set off to Jolly Joe's in which they learn Robert took the prince and wants to kill the prince and princess and anyone who stands in his way. They also learn that to find his fortress, they must find a cave past The Rocks of Malabar to find clues to his fortress.
Once they get there they find the clues but Sedgewick finds Cheese Curls and decides to stay on the island instead of going to save the princess. George and Elliot learn that Robert's men took there boat and captured the princess. They head out to follow the clues (go east to The Isle of Walking Rocks, and go through The Clapping Pass)
Sedgewick is turned on by the cheese curls and discovers he can do anything without giving up. George and Elliot get to the isle and the rocks start to surround them but Sedgewick shows up and the cheese curls start to chase him,the rocks find the curls amusing and start to interact with them.
The pass opens and one of the rocks helps them get through it. A giant mechanical serpent attacks them and George and Sedgewick are terrified, and Elliot learns he can confront anything he's afraid of.
They rescue the prince and princess only to be stopped by Robert. George learns he can stick up for himself and they escape, but Robert gets his ship and starts firing cannonballs at them, but The King shows up and sinks Robert's ship.
The king gives them medals for their good work. They go back to the restaurant only to realize that Robert stowed away on their trip back. They have a final showdown with him and send him back to his own time. Everyone loves them and they get a chance to be in the show but they refuse saying that life has plenty of adventure of its own. But then another helpseeker lands right behind them, they seem bummed but then all smile.
This is the only VeggieTales film that doesn't have any biblical references in their story neither have any references to God.