The adventure begins with an aging king named William who has a baby daughter named Odette and a friend of Queen Uberta. While King William's newborn daughter Odette and Queen Uberta's toddler-aged son Derek get acquainted, evil was afoot. Rothbart is an evil enchanter who desires King William's kingdom for himself. Before he can go ahead with his plot, his tower is attacked by King William's men. Before he was banished from the kingdom, Rothbart vowed that one day, everything King William owned and loved will be his.
When Odette and Derek are children, King William and Queen Uberta decide to have Odette and the Queen's son, Prince Derek meet every summer with hopes they'll fall in love so as to unite their kingdoms. In the meantime, Murphy, Tyler, and their team split up to protect the children from a mysterious threat that has been wreaking havoc in the kingdom. At first, while Odette and Derek are still children, their plan fails miserably, but as years pass and the two reach young adulthood, they finally begin to strongly fall madly in love. However, during a royal ball, Derek expresses his wish to marry Odette just for her beauty, which upsets her into rejecting him again. She leaves the next day with her father, Shine, Glitter, Rae, and Johnny, but they are intercepted en route by Rothbart who transforms into a "Great Animal" (a hybrid monster with the head of a wolf, the mane of a lion, the body of a bat, the feet of an eagle, and the tail of a lizard). And he is not alone. With him are four mysterious warriors made of stone. Crogulor the crocodile, Hoja the hyena, Bruto the Rhino, and Veneno the cobra. They kidnap Odette and fatally injure William. King William's captain returns to Queen Uberta's castle and informs everyone present that they were attacked by a Great Animal and Dark Warriors with evil powers. Murphy, Tyler, Benny, Leo, and Derek arrive on the scene where William tells them with his dying breath that they were attacked by a Great Animal that is "not what it seems". Despite Uberta's efforts to find another princess for her son to marry, Derek becomes fiercely determined to find Odette. He Murphy, Tyler, Benny, Leo and his best friend Bromley practice hunting each day to hopefully kill the Great Animal and save Odette.
Elsewhere, Rothbart and Crogulor have taken Odette, Shine, Glitter, Rae, and Johnny to their castle lair at Swan Lake and cast a transformational spell on her that makes her turn into a swan during the day and a human again during the night. The spell can only be broken by a vow of everlasting romantic love. Rothbart asks Odette to marry him every night so he can rule William's kingdom legally, as taking it by force is too much trouble, but she always refuses. In the meantime, Crogulor attempts to persuade Shine, Glitter, Rae, and Johnny to join him so that they can destroy Murphy and achieve their goals for power. They always refuse.
During their captivity, they befriend an old turtle named Speed, a frog named Jean-Bob, and Puffin, a puffin bird. They also meet a white dragoness named Jade, who was taken prisoner. Puffin, after learning about the workings of Rothbart's evil spell, devises a plan to reunite Odette with Derek, and Shine with Murphy. Together with Puffin, Odette and Shine find Derek and Murphy, who have gone searching for her with Bromley and the rest of the Dragonstar Squad; however, he mistakes Odette and Shine for the Great Animal and one of the Dark Warriors and tries to kill her. The ensuing chase leads Derek and the Dragonstar Squad to Swan Lake, where they witness Odette and Shine change from swan to their normal bodies. The lovers share a happy loving reunion, but almost immediately, Rothbart and Crogulor come calling. At Odette and Shine's insistence, Derek and Murphy and their team leave with the hopes of meeting the rest of the team at a ball being held by Uberta the following night. Unfortunately, Rothbart and Crogulor find Derek's bow (which Derek left behind), tell Odette and Shine that there will be no moon the next night, and have them, in swan form, imprisoned within the castle dungeon along with Bromley. He then plans to send his hag sidekick Bridget, disguised as Odette, to the ball instead, while Crogulor will conjure fake replicas of the team.
The next day, Murphy and his friends discuss the mystery of “Crogulor”. Murphy looks in a book of Aramalian history and finds out the truth behind him. Crogulor was once an general of Murphy’s father, King Lorosius. But Crogulor went powermad and attempted to release the demon, Darkfa, from imprisonment with Hoja, Bruto, and Veneno. But they were foiled and turned to stone.
After discussing what to do, Murphy and Tyler are visited by their old friend, Ignitus the Dragon, and their old mentors, Mshauri the leopard and Paarthunax the dragon. They teach Murphy and Tyler a technique called the “Super Fury” to defeat Crogulor and his generals. They also reveal that Maleficent, an old enemy of theirs, has been resurrected and revived them. They then reveal that Jade is Tyler’s long lost sister. Murphy and Tyler vow to defeat the generals and free Jade.
Odette and Shine's friends free them, but when they reache the ball, they sees that they have been replaced and try to warn Derek and Murphy; they fails, partly due to Bridget and the fake Shine's attempts to keep Derek and Murphy from seeing them, and Derek makes the vow to Bridget as Murphy makes the vow to the fake Shine. Rothbart, Crogulor, Hoja, Bruto, and Veneno arrive and reveal that Derek and Murphy's vows, given to the wrong women, will cause the spell to kill Odette and Shine. The girls fly back to Swan Lake as Crogulor and Rothbart's curse drains thier life force while Derek, Murphy and the rest of the team, desperate to save their friends, race after; they arrives too late, and Odette dies in Derek’s arms, but not before she tells him she loves him. Shine and Murphy share loving words and a kiss before Shine dies in his arms. A furious Derek confronts Rothbart, demanding that he not allow Odette to die. Murphy and his team confront Crogulor and the Stone Generals, demanding that they bring Shine back.
To their surprise, Rothbart transforms into the Great Animal and an intense battle ensues with Rothbart overpowering Derek and nearly killing him. Fortunately, Odette's animal friends return Derek's longbow to him, and Bromley, who has escaped the dungeon, provides Derek with a single arrow; Derek catches it and fires the arrow straight-and-true into Rothbart's heart as he explodes upon crashing into the lake. While Derek fights Rothbart, the team fight the Generals and defeat them. But the stone warriors get back up and are strong as before. Murphy and Tyler use the Super Fury, destroying Crogulor and his Generals once and for all. Maleficent herself appears and attempts to destroy the team, but she is beaten back and vows revenge.
With Rothbart and Crogulor's defeat, his spell on Odette and Shine is broken and she returns to life to hear Derek say that he truly does love her for her courage and kindness and always had. Shine too is revived and she and Murphy kiss.
The two are soon married and live happily ever after. Murphy proposes to Shine, asking her to be his wife and future queen. Shine is overcome with joy and says yes. The two share a romantic kiss. Tyler, in the meantime, is reunited with his sister and they promise to remain together.
Meanwhile, Murphy Dragonstar’s archenemy, Malefor, plots another scheme and brings his apprentice, Griffin, and General Berdan together before their master, where they discuss their next move.