Uzumaki Naruto, Haruno Sakura, Yamato and Sai are assigned on a mission to capture Mukade, a missing-nin. They all have Chakra Blades, which are used to attack. They set out for the once glorious historic ruins of Rōran, a city with once thousands of towers and is located in the middle of the desert. They pursue and corner the missing-nin. Mukade's goal is revealed to travel to the past and take over the Five Great Shinobi Countries with the power of the Ryūmyaku, an ancient chakra flow deep underground Rōran. He unleashes the power of the Ryūmyaku, which is seen to have been sealed by Minato's Flying Thunder God Kunai. A light envelopes Naruto and Yamato, who were trying to stop Mukade. Sakura attempts to follow them into the light, but Sai stops Sakura getting sucked into the Ryūmyaku by catching her on his ink bird while she cries out Naruto's name.
Namikaze Minato, twenty years prior to the present, is now seen at Konoha, and Jiraiya shows Minato that he has completed the Rasengan. Then the young Shizune, Gai, Sarutobi Asuma, and Hatake Kakashi are waiting in a long line at the grand opening of Ramen Ichiraku. Sarutobi Hiruzen has heard of Anrokuzan's evil plans, and sends Minato Namikaze, Shibi Aburame, Chōza Akimichi, and upon Minato's request, Kakashi, to put an end to his plans.
When Naruto awakens, he meets a mysterious young girl who immediately runs away upon seeing him. Naruto later comes into contact with a masked guy who rescues him from puppet army. He tells Naruto that he too is a Konoha ninja, opening a part of his mask to show the Konoha sign on his head protector, and tells him to leave the city. Naruto agrees to do so. Nevertheless when he is about to leave Rōran, Naruto remembers what happened before he lost his consciousness and decides to look for the others instead. Later, he realises that there is a festival going on and spots the young girl he previously encountered, now realising that she is the queen of Rōran, Sāra. When she greets the excited crowd who is calling for her joyously, someone pushes her back, causing her to fall. Naruto rescues her and then they introduce themselves to each other after Sāra mistakes him as a bad guy. Naruto asks her whether there are people who are after her, the young queen immediately disagrees with it, saying that Naruto has seen for himself that the crowd was very happy to meet her.
Later, Naruto meets Minato again in the queen's palace. Minato scolds him for not keeping his promise, but Naruto tells him that he has no choice and tells him what has happened to him. Seeing the circumstances, Minato and his team reveal themselves and that time Naruto remarks that Minato looks a lot like the Fourth Hokage. Shibi tells Naruto it is impossible, as for now the ruling Hokage is still the Third. But Chōza disagrees, saying that as Naruto is from the future, it is possible that Minato is really the Fourth. Minato simply replies that there is no point in making life less interesting by knowing things that they shouldn't. Minato then tells Naruto the condition at Rōran, and tells him that he should be able to go back to his time after he defeats Mukade. After that, he gives Naruto his Flying Thunder God Kunai, telling him that it is a special kunai that will allow him to transport to Naruto's place if he uses it.
It's later revealed that Mukade travelled to the past six years before Naruto did, by this point he's changed his name to Anrokuzan and serves as the minister of Rōran. Sāra refuses to believe that Anrokuzan is planning to overthrow her, but hestitating after Naruto points out the fact that there is indeed someone who is after for her life. Sāra, much annoyed, leaves the place. Minato tells Naruto to protect her as he continues on the mission. Naruto agrees.
When Sāra is walking alone along the palace corridor, someone strikes her from behind and takes her into a dark room, filled with a large group of people. They insist Sāra to return it, much to her confusion. Naruto enters the room to her aid, only to discover that the group is actually a group of women and children and they don't mean to hurt Sāra at the first place.
Walking along the city, suddenly a child from the group says that Sāra is said to be a "puppet princess", only to be scolded by the leader of the group. Sāra then asks her about the rumour, to which she says that it is quite true. She then tells Sāra that most of the men of Rōran were enlisted to work for the city by the queen's order, to which Sāra replies that she never gave such order and from her palace, the people seem to be happy to see her. The leader then tells her that no one actually is happy. While staring at the crowd who is calling for Sāra, the group realises that a puppet has taken over Sāra's place and greets the crowd, much to her shock. Naruto notices there is something wrong with the crowd and reveals that the "joyful" crowd are all puppets that are controlled by Ryūmyaku's chakra, with a puppet of Sāra herself appearing on the balcony above. Sāra then realises her minister's evildoing. She then promises that she would rescue the people used by him.
Naruto and Sāra find the centre of Anrokuzan's evil plan. They infiltrate the factory and find all the men who are chained and forced to work to produce puppets. Confronting Anrokuzan, Sāra orders him to release the people there, to which he laughs and says Sāra is a "puppet princess". He then confessed that he had killed Sāra's mother Sēramu, the previous queen, because she had seen through his plan and refused to work with him. Now, as Sāra is no use to him anymore, he is going to kill her and take over the world. Naruto tells Sāra that he will protect her. The Puppet Ninja Force, which is under Anrokuzan's control, can attack using the Ryūmyaku's chakra, and are able to throw kunai. Naruto is seen using his chakra-knife to attack them.
Later Anrokuzan is seen to be a giant puppet, he's able to use parts of the towers of Rōran to repair himself from any attack, which is part of his regenerative technique with the power of the Ryūmyaku. Shibi and Chōza are not able to defeat him as he keeps regenerating himself. Shibi then passes a message to Naruto and Minato, who are guarding Sāra and the citizens to the garden, the source of Ryūmyaku, where Anrokuzan cannot reach because it is heavily defenced. When battling Anrokuzan, Naruto uses Rasengan, much to Minato's shock. Naruto is easily defeated by Anrokuzan, and Minato comes to his rescue just before Anrokuzan deals the final blow. Minato then tells Naruto to follow the citizens while he is holding back Anrokuzan from reaching them. Naruto agrees, but then asks himself why he always follows Minato's orders.
Meanwhile, Minato is able to locate Anrokuzan's weakness but only to find that he cannot match the speed of his regeneration. Anrokuzan is able to get past him and aiming to kill Sāra who is planning to seal off Ryūmyaku for good. Minato then meets Naruto and tells him that he already figured out how to defeat Anrokuzan and he needs Naruto to perform Rasengan for him. When Naruto says that he has not enough chakra left, Minato tells him that he will lend him his chakra. Naruto says it is impossible, that the only people who are able to perform Rasengan are Jiraiya, himself, and the Fourth Hokage. Minato smiles and tells Naruto that he is also able to perform Rasengan while effortlessly forming a Rasengan before Naruto. He then hands over his Rasengan to Naruto and forms another Rasengan, forming a new Rasengan as he tells Naruto that similar chakra tends to synchronise each other, enhancing their powers. Sāra seals off most of the Ryūmyaku in time, making Anrokuzan unable to use his regenerative technique. Minato goes off and tells Naruto that this is the time to attack him. Naruto succeeds in hitting him. Anrokuzan states that this won't be over. As the floor crumbles, he falls down into a pool of the Ryūmyaku. Sāra is still seen on the crumbling floor, Naruto manages to catch her, but falls in too along with Minato. Yamato, who is holding on to Kakashi, comes and uses his Wood Release to catch Naruto, Sāra and Minato. Minato asks Naruto to give back his kunai to completely seal off the Ryūmyaku. A bright blue light shines as Minato seals the Ryūmyaku.
Naruto and Yamato's bodies begin to glow. Minato says since that Anrokuzan is dead his spell wore off, which means Naruto and Yamato will return to their time. When Yamato meets Minato, he bows to him and states that it is an honour to be able to meet him. Naruto is about to tell Yamato that Minato is the 4th Hokage but is interrupted by Minato who says it is time to say farewell. In order to prevent history from changing, Minato says that it is best to erase everybody's memories. When Naruto asks Minato whether he has something to tell him, Minato replies that they're out of time. Naruto then begs him to tell him now because they may not have another chance. Minato says that he is sure one day they would meet again and that time, Naruto would know what he wants to say. Naruto begins to ask if Minato can possibly be his father, but Minato interrupts him and replies that if he ever had a son, he wishes that he would grow up into a ninja like Naruto. Sāra then tells Naruto that she'll never forget what Naruto taught her. While Naruto and Yamato begin to fade, Sara smiles at Naruto and utters his name for the last time.
In the present time, the Ryūmyaku that was unleashed by Mukade, fades away. Sakura is still seen on Sai's ink bird crying out Naruto's name. When the light fades, Naruto and Yamato appear but, as Minato had said, they have no memory of what happened to them.
Outside the ruins, the team is approached by a young girl, who resembles Sāra, who claims that she felt a disturbance on the Ryūmyaku. The girl says she's the daughter of the former Queen of Rōran, which was destroyed during the war. The girl bears a Konoha Chakra Blade and tells them that her mother received it from a hero in a dream, Naruto then notices that his own Chakra Blade is missing.
As the girl and her people leave the ruins, Naruto claims that he has the feeling he saw her in a good dream. Sakura then grabs and pulls on Naruto's ear and yells at him for being a pervert.
- Junko Takeuchi as Uzumaki Naruto
- Chie Nakamura as Haruno Sakura
- Satoshi Hino as Sai
- Rikiya Koyama as Yamato
- Toshiyuki Morikawa as Namikaze Minato
- Mutsumi Tamura as Young Hatake Kakashi
- Fujiko Takimoto as Sarai & Young Sarutobi Asuma
- Mayuki Makiguchi as Young Maito Gai
- Hidekatsu Shibata as Sarutobi Hiruzen
- Kenji Hamada as Aburame Shibi
- Nobaki Fukuda as Akimichi Choza
- Hochu Otsuka as Jiraiya
- Masako Katsuki as Tsunade
- Keiko as Shizune
- Yuko Kobayashi as Masako
- Saori Hayami as Sara
- Yumi Touma as Seeramu
- ??? as Sara's Daughter
- Fujiko Takimoto as Sarai
- Ryuzaburo Otomo as Mukade/Anrokuzan
- Maile Flanagan as Naruto
- Kate Higgins as Sakura
- Troy Baker as Yamato
- Ben Diskin as Sai & Young Guy
- Tony Oliver as Minato
- Dave Wittenberg as Young Kakashi
- Doug Erholtz as Young Asuma
- David Lodge as Jiraiya
- Debi Mae West as Tsunade
- Megan Hollingshead as Shizune (Young & Older)
- Steve Kramer as Hiruzen
- Michael Sorich as Choza
- Crispin Freeman as Shibi
- Laura Bailey as Masako
- Eden Riegel as Sara & Sara's Daughter
- Mary Elizabeth McGlynn as Seeramu
- Lucien Dodge as Sarai
- J.B. Blanc as Mukade/Anrokuzan
- Its theme song is "If", a hit song sung by Kana Nishino.
- According to the movie's soundtrack list, the song Sāra and her mother use to sang together is called "To Light".
- The movie which takes place twenty one years before the series time line shows Ramen Ichiraku's grand opening. However the Third Databook states that the restaurant was actually opened approximately thirty-four years before the start of the main storyline.
- Jiraiya has a model of Kushina being preganent with Naruto during the end credits.
- During the Nine-Tails' attack on Konoha, Hiruzen's hair was depicted as brown. However in this movie, Hiruzen's hair is depicted as white, even though it took place long before the Nine-Tails' assault.
- The film states that Jiraiya was the one who created the Rasengan, whereas it had been previously established that Minato was the one who did so.
- Along with the film, a comical short feature named Naruto, the Genie, and the Three Wishes, Dattebayo! (劇場版NARUTO-ナルト-そよ風伝 ナルトと魔神と3つのお願いだってばよ!!) was shown.
- An ani-manga version of the film was release in Japan on July 16, 2010.
- A light novel adaptation written by Masatoshi Kusakabe was release in Japan on August 3, 2009.
- The poster of the film can be seen in Naruto Shippuuden episode 170.
all information on Naruto Shippuden movie 4 is from http://naruto.wikia.com/wiki/Naruto_Shipp%C5%ABden_4:_The_Lost_Tower