Prologue

Scooby-Doo and Shaggy arrive in Arabia on a magic carpet to become royal food tasters for the young Caliph. After getting hired, they eat everything in sight and leave no food for the Caliph, who, along with the Royal Chef, gets angry and orders his guards to kill them. Shaggy and Scooby-Doo find a place to hide, and Shaggy takes on the disguise as a harem girl. The Caliph, who is looking for a bride, falls in love with the disguised Shaggy and decides that they shall be married. Hoping to make the Caliph fall asleep so they can make their escape, Shaggy tells him two stories.

Aliyah-Din and the Magic Lamp

The Sultan of the land is worried as his son, The Prince, has not yet chosen a bride to marry; so he decides to have every eligible woman arrive the next day. However, the Prince notices a young woman near a river washing her clothes and falls in love with her. After seeing him, she runs off, leaving her scarf behind.

Meanwhile, Haman the vizier is trying to become Sultan. He learns of a magical lamp hidden in a cave that is revealed every three years during a blue moon. However, only a person pure of heart can enter the cave; that person being Aliyah-Din, the woman the Prince longs for. Haman finds Aliyah-Din and tells her about the lamp, saying its powers can help heal the sick Sultan.

While searching for Aliyah-Din, the Prince also attracts attention from many women who seek to marry him. On her way to meeting with Haman, Aliyah-Din discovers the news that the Prince shall choose a bride the next day. She and the Prince then bump into each other. Despite loving him, she remembers her duties to the supposedly sick Sultan and is forced to leave.

At night, Aliyah-Din meets with Haman where they witness the cave opening. Aliyah-Din enters it and finds the lamp. However, the cave starts to collapse and soon closes, leaving her and the lamp trapped inside. Aliyah-Din then rubs the lamp which releases Yogi Bear, a Genie, and his sidekick Boo-Boo, a Genie-in-training. Now she is their new master, and they can grant her three wishes.

Back at the Palace, Haman creates a potion that makes the Sultan fall into a deep sleep. When the Prince notices his father's condition, Haman puts him under the same spell. Haman then brings the unconscious Prince to the dungeons before taking on his appearance.

Aliyah-Din then goes to the palace after wishing to become a princess. Haman reveals himself, takes the lamp, and has Aliyah-Din thrown into the dungeon. Haman uses his first two wishes to make himself sultan and ruler of the whole universe. Aliyah-Din escapes from the dungeon and removes the lamp from Haman's grasp, leaving him without a third wish. Aliyah-Din gets a do-over of three wishes and uses her first one to bring everything back to normal.

With everything restored, The Prince regains consciousness and orders the palace guards to arrest Haman. The Prince then reunites with Aliyah-Din and returns her scarf before asking her to marry him. The now-awakened Sultan arrives and the Prince introduces his father to Aliyah-Din and reveals his desire to marry her. The Sultan, however, cannot bless their union, as his son can only marry a princess.

Saddened, The Prince apologizes to Aliyah-Din. However, upon learning her name, The Sultan realizes that Aliyah-Din is the long-lost princess the Prince was engaged to and allows them to be married. The Prince and Aliyah-Din celebrate their engagement and kiss, as Boo-Boo becomes a full-fledged Genie.

Interlude

After the first story, the Caliph, still awake, starts to make plans for the wedding by having the Royal Dress Worker pick out a dress. Scooby-Doo posing as the Royal Dress Worker's assistant to measure out a dress. Afterwards, Shaggy begins the next story.

Sinbad the Sailor

The second and final tale is about how Sinbad the Sailor mistakes a pirate ship for a cruise ship. Abandoned by his own crew, the maniacal pirate captain takes advantage of Magilla's situation and passes himself off as a cruise director with the plan to use Sinbad for stealing a rare rhuk egg from its nest, jewels from the Stream of Precious Gems, and a golden toothbrush (owned by a rich cyclops), passing off the thefts as being part of a scavenger hunt.

Finale

Before Shaggy can escape, the Caliph decides to start the ceremony. When the wedding cake arrives, Shaggy pigs out, and his ruse is discovered by the Royal Chef. However, since the Caliph enjoyed listening to the stories and was distracted from his hunger, he decides to make Shaggy and Scooby royal storytellers which the duo happily accept as well as maintaining their royal food tasting job. Shaggy, Scooby-Doo, the Caliph, and the Royal Chef then eat the cake.