The film opens with a wall of exposition. Long ago, a nine-tailed fox attacked the Earth and sunk Atlantis. Hope seemed lost until a man named Minotaur Namikaze appeared and defeated the fox. He then feasted on its chakra meat and used the power he gained to build five hidden villages: the Leaf Hidden Village, the Sand Hidden Village, the Dirty Hidden Village, the Cloud Hidden Village, and the Mist Hidden Village. Every five years, the Ninja World Tournament is held to (somehow) honour Minotaur's achievements.
In the present day, the Leaf Hidden Village is hosting the Ninja World Tournament. The film proper begins with a fight between Nojo Hyuga and his sister Hanto Hyuga. Hanto taunts Nojo and attacks him, but he makes a pun so bad that it knocks her out. Their father Hiashi Hyuga, who is watching from the spectator's booth, decides to have Hanto executed because she lost. He sends his mercenary Choze Akuro into the ring to finish Hanto, but resident superhero S Bugman drops into the ring. He grabs Hanto, loads her onto his motorcycle, and drives her away to safety. Choze is disappointed that he didn't get to kill anyone, and he cries.
In the next match, Sasteke Uchiro fights Shakemar Nar. Shakemar doesn't realize that he's in a fight because he's too busy listening to music on his headphones. He eventually gets gunned down by a frustrated Choze. Sasteke is angered and attacks Choze, who hops in a car and drives away. Aoba Croze then appears and reminds Sasteke that he has the somehow reborn nine-tailed fox in him. Sasteke glares at him and swears vengeance on Choze.
Meanwhile, a boy named Naruto Uzumanki, our protagonist, is running through the streets. He sees Intro Yakuza, daughter of the leader of the Yakuza Clan, in an alley, and for kicks he knocks her out with a garbage can lid. By doing this, he manages to save a man she was chasing, and he crashes at Naruto's penthouse. He introduces himself as Anko Mitarashi, but suddenly collapses on the floor. Naruto's butler, Joe Noodles, examines him and figures out that Anko is a robot. After getting new batteries, Anko explains that he has a file on the evils of the Hyuga Clan. He entrusts it to Naruto, who hides it under his pillow. He then tries to break it to Anko about him being a robot. An angered Anko refuses to believe him and runs away.
Inoichi Yakuza, leader of the Yakuza, is seen paying a mercenary named Sakura Haruno to kill Naruto because Naruto put his daughter in a coma when he hit her with the trash can lid.
That night, Barrack Obama is sitting in the White House talking with Joe Biden. He explains that he is a space alien and he wants to cause a global war so that the inhabitants of his home planet can see it from space. Suddenly, Joe Biden is frozen solid. A masked woman walks in and introduces herself as Jack Frost because smashing Biden with a hammer. She then tells Obama that his days are numbered before leaving.
The next day, Naruto's teacher Mizuki brings him donuts. His other teacher, the evil Iruka shows up with vegetables, but Naruto refuses to eat them. Naruto heads out to the store and Sakura attacks him with a knife in the streets. She is taken down by a nearby cop named Asuman Sarutobi, who explains that he's investigating the Yakuza Clan.
Meanwhile, a man known as Kakashi of the Mysteries is summoned to the Fire Lord's tower by the village leader, Hiruzen Sarutobi. There, Hiruzen explains that Sasteke and Nojo are doing well at the Ninja World Tournament, but not in the popularity polls. He shows Kakashi a video of Rocky Lee, a favourite to win, and his mentor Mighty Shimura. He then says that he will have Kakashi take Nojo and Sasteke on a vacation so that they don't win. Kakashi notices an incredibly dangerous book of satanic rituals in a glass case and flashbacks to when the incredibly evil ninja Madata Ichiko was attempting to use a similar book to summon demons from hell. Kakashi's teammate Obito Uchiro easily took him down, but died from eating tainted food the next day. After Hiruzen leaves the room, a girl named Teno Tei smashes the glass case while playing with a shuriken.
Meanwhile, Hiashi was so impressed with Sakura's failed attempt to kill Naruto that he hired her to.......kill Naruto. It is never explained how Sakura got out of jail. He also sends Choze and another man named Kira Kibbles to kill Naruto.
Later that day, Hiruzen tells the citizens of the Leaf Hidden Village over loudspeaker that a masked man named Tobi nuked France, where the Dirty Hidden Village was located. The leader of the Dirty Hidden Village committed suicide when he read about it in the newspaper. This creates widespread panic, and someone bombs the Ninja Academy for some reason. Tobi and his henchman Baki can be seen watching the riots.
Kakashi is seen eating in a restaurant with the book of satanic rituals. Nojo is eating with him, and explains to Kakashi that Kakashi has forgotten what happened to Rin after Obito died. They leave the restaurant to find Sasteke, but Kakashi forgets the book and it is stolen by Iruka.
Iruka appears at Naruto's house with the book and tricks him into reading a satanic ritual that summons an evil demon named the Sandman. The Sandman kills Iruka, then kills Mizuki when he arrives to save Naruto. Kakashi and Nojo arrive and chase off the Sandman with maracas. Kakashi hides under the bed when a thunderstorm starts, and then the three assassins Hiashi sent burst into the room. Before they can do anything, Sasteke arrives. A fight starts, and Sasteke kills Sakura and Kira, but Choze gets away. Hiruzen then shows up and uses the Sandman's release as an opportunity to send Naruto, Nojo, Sasteke, Kakashi, and Joe Noodles off to England.
On the way back to the Fire Lord's tower, Hiruzen is ambushed and killed by Tobi and Baki. Tobi then pulls out his phone and calls Kurenai, the queen of China. He explains that he needs more weapons if he is to destroy the Leaf Hidden Village. Kurenai tells him that she will have her underlings make bombs, shotguns, tanks, and water balloons. She will then smuggle them in to London and hide them in Buckingham Palace. Tobi compliments her on her convoluted plan and begins planning how he will break in to Buckingham Palace. Meanwhile, Choze finds Anko moping and reprogams him to be loyal to Hiashi.
The next day, Naruto, Nojo, Sasteke, Kakashi, and Noodle Joe leave the Leaf Hidden Village on a boat. The boat somehow makes it to just outside of Britain in a day. However, Jack Frost lands on the boat, followed by her fellow Frost Clan members Kankura and Tomato. Jack Frost removes her mask, causing Nojo to gasp and yell, "It's you!" However, he doesn't actually know who she is. Jack Frost then explains that the American Government murdered her children to film a propaganda film, and thus she will destroy the world. A fight ensues, and one of the ship's crew snaps pictures of it from a higher vantage point. Jack Frost gains the upper hand, but the photo-taking crew member soon intervenes. He explains that his name is Kabuto, and that the ship has arrived in Britain. Naruto's team departs, while Jack Frost stands there flabbergasted. Kabuto slowly approaches Kankura and then tears off his arm.
Back at the Leaf Hidden Village, Rocky Lee is getting a pep talk from Mighty Shimura about how he must not reveal his secrets to the other ninja. However, this is interrupted when Aoba announces to the ninja attending the world tournament that Fire Lord Hiruzen was murdered. Hiashi gives a speech about how a new era shall come with him as king and everyone else crushed underfoot. This gets a round of applause for whatever reason.
Meanwhile, Naruto's team arrive in London, where the Sandman has been spotted. They are immediately attacked by the Sandman, but are saved by Baki of the Dark, who has realized the error of his ways. However, the Sandman immediately assimilates him, gaining more power in the process. He then transforms into sand and flies off. Tobi then walks up to Naruto and tells him that soon the world will be destroyed.
Cut to Choze making a bomb out of the bodies of Sakura and Kira. Anko and Hiashi walk in and tell him that he needs to hurry up and build the bomb faster so that Hiashi's evil scheme can work.
Meanwhile Asuman, believed Naruto to have been kidnapped, investigates the penthouse where Naruto lives. Under Naruto's pillow, he discovers the file containing evidence of the gross human rights violations committed by the Hyuga Clan. He leafs through it, interested.
Back in London, Nojo wants to see the Eiffel Tower being airlifted into London. However, Naruto starts whining about his life and how no one understands him. Sasteke then explains that his family was murdered by Mighty Shimura, who was never prosecuted because he wrote Hiruzen a note saying, "I'm sorry." Nojo then explains that his father Hiashi has attempted to murder him every single day of his life since he turned four. Noodle Joe explains that before he was Naruto's personal servant, he was a slave in Africa for fifty years. Kakashi nods silently. Naruto then runs off crying.
As he is running, Naruto gets tackled by Sonic the Hedgehog. Sonic tells Naruto not to be a whiny bitch and runs off. Then Goku and Sokka appear and tell Naruto that the Saiyan Biker Gang is rising, and that Goku will have to fight their leader Prince Vegeta in Dragon Ball Z Evolution 2: Rise of the Saiyan Biker Gang
. After their ad for the movie is done, they leave. Naruto then decides to visit Buckingham Palace.
Back at the World Tournament arena, Rocky Lee is fighting a man named Jiraiya. Rocky Lee effortlessly defeats him, earning the cheers of the audience. However, the stadium is suddenly attacked by Jack Frost, Kankura (who has his arm back with no explanation given), and Tomato. Jack Frost begins freezing random people, causing Rocky Lee to mutter under his breath, "I'm sorry Mighty Shimura, but I have to." He then reveals his secret: he's actually a bear wearing a human suit. He pulls off his latex mask and attacks Kankura, who slaps him. However, Kankura is then immediately arrested by Captain Asuman after Animal Rights Activists yell at him. Jack Frost and Tomato flee. Hiashi then stands up and tells the people gathered that they need strong leadership in such troubling times, and that, "a fascist, genocidal, war-mongering dictator such as me would be perfect for the job." The people applaud again.
Back at London, Sasteke, Kakashi, Nojo, and Noodle Joe are watching the Eiffel Tower be lowered down into the city. However, the Sandman and Tobi appear. The Sandman explains that they realized that since both of them were evil, their goals were the same. Thus, they decided to team up. The Sandman then fuses with the Eiffel Tower and turns it into a giant laser. He then carves a Slasher Smile
on the moon. Nojo attacks him, but Tobi blocks his attack and a battle ensues.
Meanwhile, Naruto wanders into Queen Elizabeth's room and attacks her. When the Queen asks what he's doing, Naruto accuses her of being an imposter. The Queen reveals that she really is an imposter, and morphs into Anko. Naruto gasps, and Anko explains that now that Choze has reprogrammed him to make him serve Hiashi, he is evil. Naruto starts to fight Anko, but then Hiashi manually overrides Anko. Rocket boosters come out of Anko's shoes and he flies through the ceiling and back towards the Leaf Hidden Village. Naruto then searches the room and finds a shotgun hidden under the Queen's mattress (by Kurenai) and the Queen tied up in the closet.
Anko flies down into the Fire Lord's tower. He then hooks himself up to a speaker and says to the Leaf Hidden Village that he has a bomb inside his body, and will blow up the Fire Lord's tower and kill everyone inside it. Ibiki Morino and Hayate Gekko, two random bystanders, try to breach the police barrier set up, but a piece of the moon that was carved off by the Sandman's laser falls on Ibiki and kills him. Hayate screams and runs away. Meanwhile, Jack Frost and Tomato are walking down the street when they see a cat crying over Anko's promise to blow up the Fire Lord's tower. This biological impossibility convinces Jack Frost to change her side and not want to destroy the world. She has Tomato use her wind powers to launch her over the police barrier and into the tower. There, she sees Anko pointing a gun at Aoba and saying that he will no longer rule the village.
Back in London, Sasteke is fighting Tobi. Tobi taunts Sasteke about not wanting to use the full power of the fox. Angered, Sasteke transforms into Renamon and smashes Tobi's mask. After a montage consisting of the one scene Teno Tei was in seen from several angles, Tobi is revealed to be Teno Tei. With her identity revealed, Teno Tei promises to destroy the world and then flees. Nojo and Kakashi then attack the Sandman-Eiffel Tower, but it has no effect. The Sandman-Eiffel Tower then flies up into the sky and begins to charge up a laser that will destroy all of Europe.
Back at the Leaf Hidden Village, Jack Frost briefly fights Anko. This distracts him long enough for Aoba to get away. Jack Frost then freezes herself and Anko solid, neutralizing the bomb. Aoba runs and calls out to Asuman that the bomb has been neutralized. Asuman then says that he sticks to routine, and has already called in a nuclear strike on the Fire Lord's tower. Aoba tells him to call it off, but Asuman shrugs and says that he has no regrets. The Fire Lord's tower then gets nuked, vaporizing it completely and killing Aoba, Anko, and Jack Frost, but not harming anything else for some reason.
Back in London, the Eiffel Tower laser is nearly powered up. The Sandman's torso emerges from the Eiffel Tower and he smugly gloats. However, it is then revealed that Naruto has been hanging onto the Eiffel Tower the whole time. The Sandman decides to continue gloating, only for Naruto to shoot him with his shotgun. It's a perfect headshot, and the Sandman is instantly killed. The Eiffel Tower laser then begins to meltdown, and it blasts off into the sky with Naruto still hanging on. Down on the ground, Sasteke, Nojo, Joe Noodles, and Kakashi sigh with relief at the laser being destroyed.
The next day, Sasteke and friends eat breakfast at a cafe and talk about how great Naruto was, and how he was a hero who saved everyone. Then, they see on TV that Hiashi is being sworn in as the new leader of the Leaf Hidden Village. Hiashi vows to be an evil leader who will make Hitler look like a saint in comparison to the atrocities he commits. The crowd cheers.
In the Leaf Hidden Village itself, Asuman receives bribe money from one of Hiashi's goons. Asuman then shoots the goon, and proceeds to light the body and the file detailing Hiashi's crimes against humanity on fire. He walks away from the flames, smirking evilly.
The film ends with Naruto being awakened by a boy named Ichigo Jones. Ichigo explains that the Eiffel Tower crashed into his home in New York City, and that he ate the Sandman's remains and gained Soul Reaper powers. He then tells the audience that they will see more of him in the upcoming film The Legend of Bleach: THE HEART
There is an after credits scene. In it, Mighty Shimura approaches Hiashi and removes the bandages he wears, revealing that his whole arm is covered with eyes. He then bows down to Hiashi, who laughs evilly.