綱手より第四次忍界大戦の開始が近い事を告げられるサクラ。迫り来る戦争の気配を察しているチョウジに、開戦が近い事を告げるシカマル。木ノ葉の面々それぞれが、来るべき戦争を前に、守るべきものの為、静かに覚悟を決めていく。その頃、雲隠れの里では五影が集まり、今後の方針を相談していた。全体決定として人柱力を隠す条件を飲む代わりに、綱手が雷影に願った事とは…。

「人柱力を隠す」という作戦をナルトに気取られぬよう、建前上ナルトに極秘任務を与えて旅立たせる綱手。予言のタコ探しに胸を躍らせつつ、ヤマト、ガイ、アオバとともに船旅に出るナルトだが、突如その前に難題が持ち上がる。出航する湾の出口に船を襲う化物が出現する為、船乗り達が船を出さないのだという。先を急ぐ為、化物退治を引き受けるナルトたちだが――その最中、ナルト達は化物に果敢に立ち向かおうとする一人の青年に出会う。

なれない船旅のせいで船酔いになってしまったナルト、ヤマト、ガイ、アオバの一行。特にひどいのはガイで、一行はひとまず付近の無人島に立ち寄ることにする。ナルトたちはその島で、サクラ、いの、チョウジと出会う。この島は薬草の宝庫といわれる島で、サクラたちは綱手の指示で薬草を集めに来たのだ。ナルトはガイが回復するまでの間、サクラたちの薬草集めを手伝うことにするが、行く先々で見つかるはずの薬草が見つからない。それもそのはずで、薬草はすでに紅州（ベニス）という小国の商忍たちがあらかた採集したあとだった。手ぶらで里に帰ることもできないサクラたちだが、商魂たくましい商忍たちもまた、より多くの薬草を手に入れようとあらゆる手段を駆使してくる。

たちこめる濃霧のために、ナルトたちが乗る船は、海上で立ち往生を余儀なくされていた。暇をもてあました一行は、なぜか怪談話で盛り上がるが、お化けや幽霊の話が大嫌いなナルトは、強がってはみるものの怖くてたまらない。そんな中、霧の中から一隻の船が現れる。ナルトはそれが、さきほどの怪談話で聞いた幽霊船ではないかと思いおびえるが、乗っていたのは幽霊ではなく、ヒシャクという名前の少年水夫だった。だが、それなりの大きさの船でありながら、その船にはヒシャク以外の乗組員がひとりもいない。不審に思ったヤマトがその理由をたずねてみると――。

相変わらず船酔いがひどいガイが、飛んできた巨鳥に連れ去られた。ガイを助けるため、巨鳥が飛び去った方向にある島へと上陸するナルト、ヤマト、アオバ。早速、ガイの捜索を始めようとするが、そのとき三人はひとりの女性を見かける。話を聞こうと声をかけるアオバ。だが、なぜか女性は逃げるようにその場から立ち去ってゆく。思わず後を追ったアオバは、たどり着いた廃墟にあった資料から、この島に隠された恐ろしい秘密を知る。　一方、アオバと別れ、別の方向を進んでいたナルトとヤマトは、次々と現れる巨大生物やバケモノたちを相手に悪戦苦闘していた。

それは昔、ガイの愛弟子・リーが、必殺技・裏蓮華を習得したお祝いをした翌日のことだった。あまりの喜ばしいできごとに、ハメをはずして飲みすぎたガイは、途中から記憶をなくしていた。それはなぜか夕べ一緒にいたリーも同じで、ふたりとも必死で記憶の糸をたぐりよせる。そしてガイは、漠然と思い出した記憶の中からある結論にたどり着く。どうやら自分はお祝いの席に選んだ店で、酔っ払った挙句、大暴れをするという醜態をさらしたらしい。何とかして師匠の面目を保ちたいガイは、リーの記憶が戻らないようにと、いきあたりばったりのでたらめな修業に巻き込み、気をそらそうとする。

水と食料の補給のため、ナルトたちの船はとある港に立ち寄った。ヤマトの指示で食料調達に向かったナルトは、そこでひとりの野菜売りと出会い、すすめられるまま珍しいキノコを買う。ところが、港での補給を終え、次の航海へと出発した船をとんでもない悪夢が襲う。 はじまりは急に体調を崩したヤマトが倒れたことだった。その後、食糧倉庫に見たこともない毒々しいキノコが大繁殖し、食料はおろか水までもが浸食されていることが判明。だが現在いる海域の特殊な海流のせいで、先を急ぐことも陸に立ち寄ることもできない。ナルトたちのサバイバル生活が始まった!?

数日間続く嵐に翻弄されているナルト達。ナルトは影分身を動員して膨大な仕事を片付けていくが、散々いいようにこき使われ、挙句上から目線の本体ナルトの態度に、影分身達の不満が一気に爆発。本体ナルトを監禁し、待遇改善を要求すべく反乱を起こしてしまう。慌てて影分身を解こうとするナルトだが、術はなぜか解けず――仕方なくヤマト、アオバ、ガイら上忍による救出作戦が開始されるが…

大戦を控え、仲間達の命を預かる責任を重く感じているシカマル。その考えを見透かしたように、シカクはシカマルを遠方の任務に送り出す。それは航路の途中の藻屑島にて、ナルト達と合流し、物資を補給する任務だった。無事目的を果たし、島を出ようとする一行だが、突如船は霧に包まれ、羅針盤の動きが狂い始める。そして襲い掛かる幾つもの危難――なんとかやりすごして海域から脱出しようとするナルト達だが、船は同じ場所を回るばかり。しかもこの現象は幻術ではなかった。

日向一族の集まりに召集されるヒナタ。当主のヒアシは集めた面々に、第四次忍界大戦に向けた一族の体制について説明する。ヒアシは後詰め、ハナビは若すぎるとの理由から、前線ではネジが一族を纏めるよう指示するヒアシ。宗家の嫡子を飛び越えての人選にざわめく日向家の面々をよそに、恩師・紅の見舞いに向かうヒナタ。見送るネジの脳裏には、この三年間ヒナタとともに行った修業の日々が蘇っていた…。

海からはなれ、久しぶりに陸を進むナルト、ヤマト、ガイ、アオバの前に「木ノ葉隠れのうずまきナルト」を名乗る盗賊が現れた。しかしその見た目は当のナルトには似てもに似つかない。本人を前に正体がバレ、やぶれかぶれでナルトに戦いを挑む盗賊。そこへ盗賊を追っているという忍者が現れた。実はこのふたりは仲間で、出世を夢見て名前を売るため、あちこちで自作自演の大捕り物を繰り返していた。そんなこととはつゆ知らないナルトたちは、現れた男に盗賊の身柄を渡し先を急ぐ。だが、「盗賊・うずまきナルト」のウワサは思いのほか広がっており、そのせいでナルトをかたるふたりは窮地に立たされる。

大戦を前に、木ノ葉隠れの里は準備に追われていた。緊張感の高まる里の様子にいつになく気持ちがたかぶり、自分も先輩忍者たちとともに戦場で敵と戦い手柄を立てようと意気込む木ノ葉丸。だが、まだ若く、見習いの身である下忍の木ノ葉丸が戦場にかりだされるはずもない。そこで、仲間のウドンやモエギを巻き込んで、どうしたら手柄を立てられるかについてサクラやシマカルたち先輩忍者の話を聞こうとする。だが、誰ひとりとして取り合ってくれず悔しい思いをするのだった。ウドンとモエギは功を焦る木ノ葉丸のことを心配するが……。

とある港にたどり着いたナルトは、女性ばかりの忍者の里・撫子（なでしこ）の里の次期里長・シズカとその従者・トキワと出会う。聞けばふたりは自来也の弟子を探しているという。撫子の里では、里長になるくノ一が、自分と戦って勝った男を婿にむかえるというならわしがあり、数十年前には自来也が、先代里長の婿候補となったことがあった。だが、そのときは戦いの決着がつかず、ふたりは勝負を自分たちの弟子に託した。　師匠たちの勝手な取り決めにより、シズカと戦うことを強要されるナルト。だが、お互いの気持ちを無視した婿選びのやり方に納得がいかず……。

木ノ葉隠れの里で忍者アカデミーの生徒たちを指導するシノは、生徒の質問に答えるため、自分がまだ下忍だった頃の思い出を話し始めていた。

あるときシノたち第八班は、ターゲットの盗賊忍者を追い詰めたものの取り逃がしたことがあった。その原因のひとつは、シノが敵に弱点をつかれたことだった。気を落とすシノを心配するキバとヒナタ。そんな三人に紅は、里の温泉地に行くよう指示する。温泉地でキズを癒しながら、キバやヒナタと修業に励み、苦手だった接近戦にも対応できるようになってゆくシノ。そんなとき、シノたちが取り逃がした敵が近くにいるとの報せが入る。だが、自分のいたらなさで任務に失敗したことを気にするシノは、キバやヒナタの仲間として戦うことにまだ迷いがあった。

大戦に備え、リーの八門遁甲（はちもんとんこう）を強化する修業に付き合うテンテン。テンテンが放った金属人形を持ち上げるべく、滝つぼに飛び込むリーだが、なかなか水面に浮上してこない。「さっさと上がってきなさいよ、リー！」仲間の力を信じ、声の限りに激励するテンテン。滝つぼを見つめるテンテンの脳裏には、少女時代に描いていた夢と、努力と熱血で走り続けたこれまでの日々が蘇っていた。

久々の休暇に、足を伸ばして里の郊外を散策するサイ。復興が進んでいるとはいえ、まだまだ人手が足りていない状況を実感していると、壊れた建物の間で遊んでいる子供達に遭遇する。ふざけあう子供達の様子は、どこかサクラとナルトの様子を思い起こさせた。「仲間」と「友達」の違いを問いかける子供達の無邪気な質問に、苦笑するサイだが――

偶然出くわした子供達のけんかを、見事な連携で止めるいの、チョウジ、シカマル。すると一部始終を見ていた老下忍のコスケが三人の連携を褒める。以前、コスケはアスマ率いるいのシカチョウの連携術に危うい所を救われた事があったのだ。当時を懐かしむシカマル達に、コスケは木ノ葉崩しの最中にコスケの命を救った、もう一つの「フォーメーションいのシカチョウ」の話を聞かせるが…。

いつの間にか大きく開いてしまった『里の英雄』ナルトとの差に、歯がみするキバ。差を縮めるべく赤丸と共に修業に励むが、なかなか成果が出ない。思い余って、通りかかったカカシに修業を願い出るが、生憎カカシは所用に追われていた。しかしキバの思いを汲んだカカシはキバの修業相手とするために八忍犬を口寄せする。拍子抜けするものの、早々に八忍犬を倒し、カカシ本人に修業をつけてもらおうと意気込むキバはパックン達に挑んでゆくが――

最後の補給地を前に、旅の終わりが近い事を感じるナルト達。ここまで来ればもう安心だと安堵するガイとアオバだが、油断は禁物だと注意を促すヤマト。噂では最近、チャクラまでもコピーする変化の術があるという。気を引き締め、見張りに立つガイだったが――その晩、うたた寝しているガイの元に現れたのは…。

水の国領内の小島にて最後の補給を行うナルト達。同じ頃、岩隠れの赤ツチと黒ツチは水影宛の書状を携え、土影の使者として同じ島に降り立っていた。しかしそこへ突如、霧隠れの忍たちが襲い掛かる。通りかかったナルト、迎えに来た長十郎が助太刀に入るが、仲間の一人が深手を負ってしまう。この襲撃を企てたのは霧の上忍、巌流（がんりゅう）。巌流はヨスガ峠の悲劇と呼ばれる、ある事件の生き残りだった…。