The story begins with three children and a horse. Theses are young versions of Dudley Do-Right (character), Nell Fenwick, Snidely Whiplash and Horse. The three talk of their aspirations; Dudley believes he is destined to be a Royal Canadian Mounted Police officer (Mountie) while Nell wishes to see the world. Snidely, however, wishes to be the "bad guy" and travel around the world.
Several years later, all three have fulfilled their supposed destinies. Dudley is now a Mountie (but always sticks to the rules and is frequently oblivious of things), and Snidely has become an infamous banks robber. After Snidely and his gang rob a bank of its money and gold, Snidely tricks his entire gang into believing he has fled with the bulk of the cash to the Sudan and going on a wild goose chase after him. Snidely subsequently salts the stolen gold and spreads it into the lakes. Dudley catches him the act, but Snidely fools him into thinking he is vampire hunting, and uses a similar tactic to scare Horse off. Not long after, Nell returns from her world tour and reunites with Dudley. The two attend a festival at the nearby Kumquat tribe.
Meanwhile, Prospector Kim J. Darling , the poorest man in Semi-Happy Valley, stumbles across the gold in the river and is made into a media sensation by Snidely. The subsequent gold rush boosts Snidely's popularity and he quickly takes control of the town, renaming it "Whiplash City". Eventually, Snidely's men return from the Sudan to kill him for his deceit, but Snidely convinces them otherwise by offering them lives of luxury in his new town. Dudley becomes convinced that Snidely is up to something and confronts him, but Snidely laughs him off and snatches Nell from him. Snidely sends his second in command, Homer (Jack Kehler), to assassinate Dudley with a bomb, but Dudley is absent when the bomb goes off. Nell's father Inspector Fenwick (Robert Prosky), who is in good favor with Snidely, discovers Dudley's feud with Snidely and discharges Dudley from the Mounties. Dudley falls into a depression and wanders across the town until he runs into a drunken Darling, who offers him shelter at his underground cave in the woods. Darling tells Dudley of Snidely's plans and newfound popularity and takes him to see a Gala Ball in Snidely's honor. Despite Darling's warning not to challenge Snidely due to his loss of favor, Dudley comically attempts to take Nell back from Snidely, but loses pathetically.
Feeling sympathy for Dudley, Darling decides to put him through a very harsh training regimen to make him a more formidable opponent and take back Semi-Valley from Snidely. Dudley's first act is to intimidate one of Snidely's men into telling him the next gold shipment. Dudley sabotages the shipment and leaves his mark on Snidely's workshop as well as his favorite golf course. Snidely, unaware that Dudley lost his job, is offended by this and more so with his men's incompetence to stop him, believing Dudley is enjoying the perks of being the villain. Eventually, Darling leaves to find his family and parts ways with Dudley thanking him for his friendship. Dudley then uses his new training to win Nell back from Snidely, who swears revenge. At a nighttime town meeting, Snidely attempts to rally the people against Dudley, but it falls on deaf ears. The populace have grown weary of Snidely and shows more respect for Dudley in his efforts to retake their town back. Snidely ultimately discovers that Dudley and Nell are at another festival with the Kumquat tribe and leads a full-scale attack on them. The Kumquats flee for their lives until Horse reappears and helps Dudley sabotage Snidely's tanks by making Snidely and Homer accidentally shoot each other. A cavalry of Mounties appears and arrests Snidely and his men. Darling also arrives with his wife, the Prime Minister of Canada and is reunited with Dudley, revealing that they called out the cavalry. Inspector Fenwick reinstates Dudley in the Mounties.
The final scene shows Dudley and Nell living together in Dudley's rebuilt house. They share a kiss as the film closes.