The movie opens with Troubadour, a French-speaking turtle who loves songs, reminding a television-show narrator that he had promised Troubadour one of his songs would be used in the show that day. The narrator silently breaks his promise and walks away from Troubadour. He does not look where he is going and falls in a hole in the floor as the show is about to begin. Consequently, Troubadour is ushered in to tell the audience the story at the last minute, and he chooses his comic book of The Three Musketeers.
"Our story begins in the gutter", he says, where Mickey Mouse, Donald Duck, Goofy, and Mickey's dog Pluto are street urchins, who, while being robbed by masked bandits (played by the Beagle Boys) and are saved by the Royal Musketeers, Athos, Aramis, Porthos and d'Artagnan. Afterward, Athos gives his hat to Mickey as a souvenir. The urchins are inspired to be great musketeers some day. Years later, the three are working as janitors in the palace along with Sonic, Aqua, Lucario, Drake, Oswald the lucky Rabbit, Daffy, Sakura, Naruto, Conkers, Ammy, Ishunn and Shadow and also Charlie Barkin and Itchy, still dreaming of becoming musketeers, despite their flaws: Donald is a "coward" (who turns into a chicken whenever he is frightened), Goofy is a "doofus", and Mickey is "just too small", according to Captain Pete of the Royal Musketeers. This leaves the three downhearted.
Meanwhile, Minnie Mouse, princess of France, and her lady-in-waiting, Daisy Duck, are in a palace discussing Minnie's obsession with finding her "one true love". Daisy says that she must marry someone who is of royal blood, and Minnie insists that she cannot marry someone she does not love. Minnie says she will know that he is "the one" when he makes her laugh. Minnie then takes a walk in the palace garden and barely escapes with her life when the Beagle Boys and Scratch and Grounder attempt to drop a safe on her.
The Beagles run to tell their boss, Captain Pete, that they were not successful in dropping the safe on Minnie. Pete gets upset, because the assignment to take over the kingdom. (This is accompanied by a running gag: whenever Pete says "...before the opera" or ...at the opera"or "...the opera's tomorrow night", a poster of the opera is shown, and an operatic voice sings.) Just then, Pete's lieutenant, Clarabelle Cow, tells Pete that Princess Minnie requests his presence. Pete goes to the princess, who tells him that she wants musketeer bodyguards. Pete, knowing that skilled musketeers would jeopardize his kidnap plans, appoints Mickey, Donald, and Goofy along with Sonic and pals to protect her.
When the eleven "musketeers" meet Princess Minnie, she instantly falls in love with Mickey. The boys are so caught up wanting to make a good first impression that when Daisy comes in with a tray of cheese for Minnie and they see the accompanying knife, they tackle Daisy, thinking her a villain.
While Minnie and Daisy, protected by Mickey, Donald, and Goofy, and Sonic and friends go on a journey, they are ambushed by the Beagle Boys and Scratch and Grounder. Donald hides and is eventually thrown off the carriage, and Goofy is easily defeated, leaving Mickey to fight the intruders. Mickey is also defeated, leaving the three heroes stranded. Mickey and Sonic encourages his friends not to lose hope and they rush to rescue Minnie and Daisy. At the entrance to a tall tower, Goofy tells his fellow musketeers to stand back so he can break down the door, but Mickey opens it before he can stop, which sends Goofy rolling past the Beagle Boys and out of the tower. Outside, Goofy bounces off a tree, gets kicked by a cow and is thrown by a windmill back into the tower, and goes rolling past the Beagle Boys again as Sonic and friends are battling them. When Mickey and Goofy are trapped with the Beagle Boys, Goofy gets the idea to do the same thing again with Mickey, Oswald and Sonic, and they manage to knock the Beagles out of the tower and rescue Minnie and Daisy. After Mickey unties Minnie and makes her laugh, the two fall in love.
Pete is furious that the Beagle Boys failed in their task and realizes that the eleven protagonists are more of a threat than he thought. While on night duty, Goofy and some of the gang are lured away from the palace by Clarabelle. The Beagle Boys appear before Donald, Daffy, Charlie and Itchy, capture him, and try to do away with him, but he escapes and tells the whole story to Mickey before running off, leaving Mickey, Oswald and Sonic by themself. Mickey, Oswald, Sonic, and Naruto are then captured by Pete, who chains them up in a dungeon in Mont Saint-Michel that will flood when the tide comes in.
Meanwhile, Clarabelle is about to throw a chained up Goofy along with Aqua, Charlie, Icthy, Drake, Sakura, Hinata and Shadow to their death off a bridge. Goofy flirts with her, and wins her heart with his "numbskull charm". She pulls him up and they kiss. Then, they plummet towards the river, but land on Donald and Daffy's boat instead. Goofy tries to convince Donald that they have to save their frineds but he is too scared to try. An insulting song by Troubadour, however, makes them change their mind and they rescue their friend just in time. Outside the Paris Opéra, Minnie is captured by the Beagle Boys and the robotic duo and the smallest one poses as her, announcing to the public that she is handing the crown over to a gleeful Pete. Mickey, Donald and Goofy with Sonic and Friends arrive and battle Pete and new robot made by Eggman for Scatch and Grounder, finally defeating them and saving the Princess. Mickey and Minnie finally declare their love for one another, as do the others. Mickey, Donald and Goofy are dubbed royal musketeers along with Sonic and Friends as honorary musketeers.
- Guest Starring: Drake, Hinata.
- Villians: Scratch, Grounder
- Pete plans to caught Naruto's nine-tail spirit to give to someone
- This the debut of Dracoknight's character, Drake and Charlie and Itchy too since "Sonic's Adventures of All Dogs Go To Heaven 2"