由紅豆率領的探索偵查小隊跟隨兜的蹤跡來到墳場外，將兜與鳶結盟的最新情報傳信回木葉。綱手通報全村關於大戰在即，而鳴人正好被深作通靈回木葉村，告知同伴們關於自己即將遇到章魚的預言。綱手幾天後來到雲忍者村參與聯合作戰會議整合意見，然而卻得知其他四影已集體同意將鳴人和殺人蜂拘禁於某處作為保護，並封鎖消息且嚴禁他們參戰。對此反對的綱手卻只能配合各影的決定，同時私下拜託雷影讓殺人蜂教導鳴人學會控制尾獸力量；以此實現仙人的預言。至此，綱手在隱瞞戰爭詳情的情況下，指派鳴人在大和、凱與青葉等上忍的陪同，遠去雷之國的一座海島執行「S級任務」，該處既是雷影安排的拘禁地點，同時也是殺人蜂學習控制尾獸的修煉地。

為了不讓鳴人發現「隱藏祭品之力」的作戰，綱手便捏造了一個機密任務給鳴人執行，讓鳴人踏上了旅程。為了尋找預言中的章魚，鳴人與大和、阿凱、青葉等人打算搭船出海，沒想到卻被突如其來的難題給困住了。因為出航的港口出口處有隻會攻擊船隻的怪物，使得船員們都不敢駕船出海。為了趕路，鳴人一行人答應會將怪物擊退，但是就在鳴人們勇敢面對怪物時，遇到了一位青年…。

鳴人、大和、阿凱、青葉因為不習慣搭船，全都暈船了。尤其是阿凱暈船的情況最為嚴重，一行人於是決定先到附近的無人島上靠岸。鳴人們在那座島上遇到了小櫻、井野與丁次。因為這座島是藥用植物的寶庫，小櫻一行便在綱手的指示下前來採草樂。鳴人決定在阿凱休養的期間，幫忙小櫻他們採草樂，但是卻在到達指定地點後遲遲採不到藥草。因為藥草已經被一個名叫紅州的小國商忍們採走了。然而小櫻他們也不能因此空手而回，但擅長做生意的商忍們，似乎是用盡所有方法趕在小櫻他們前面，先將草樂採走。

因為久久不散的濃霧，使得鳴人他們所搭乘的船被困在海上動彈不得。為了打發時間，只好說鬼故事來娛樂一下，只是最討厭聽鬼故事的鳴人，實在難掩心中的害怕。就在那裡時候，有一艘船在濃霧中現身。鳴人一想到那會不會就是剛才聽的鬼故事中的幽靈船，就覺得害怕，結果搭乘那艘船的並不是鬼，而是一位名叫杓子的少年船夫。可是，船明明就那麼大一艘，居然就只有杓子一個人，大和覺得很可疑，便詢問杓子原因。

鳴人一行人的船在航行途中突然遭受砲擊。這座看似戰艦的島嶼，就是在附近海域橫行的海賊們的巢穴。為了從攻擊中脫困，大和運用木遁製造速成的潛水艇潛入海裡，並暫時在海底洞穴棲身。沒想到卻在洞穴裡看到令人震驚的光景…

暈船的阿凱被飛來的巨鳥抓走了，他們循著巨島飛行的方向，登陸了一座小島。在這座島上，青葉遇見了一位神秘女性，並在她的引導下，得知了隱藏在這座島上的可怕祕密…

阿凱曾經為了慶祝小李學會必殺技．裏蓮華，而舉辦了師徒兩人的慶祝會。但是在店裡喝多了的阿凱，到了隔天只記得某些片段的記憶，而小李也將前一晚的事忘得一乾二淨，為了回想起昨晚發生的事，他們展開了各式各樣的想像訓練。

為了補給水與糧食，鳴人一行人的船隻在某個港口靠岸。前往張羅糧食的鳴人，在一名賣菜小販的推薦下，買了一顆很珍貴的蘑菇。但這顆蘑菇卻害得船上的食物及飲水全都無法食用，於是一場海上求生奮鬥記就此揭開序幕。

為了與暴風雨奮戰，鳴人動員影分身幫忙處理大量的工作，在一直得不到休息的情況下，分身們決定要綁架鳴人，要求改善工作環境與待遇。面對鳴人被俘的狀況，大和、青葉與阿凱這些上忍們，只好展開救援作戰…

大戰在即，鹿丸感受到自己肩負著夥伴性命的重責大任，並為此感到迷惘。看穿鹿丸心思的四角，建議他接下與鳴人一行人會合，進行物資補給的任務。但是當眾人準備離開藻屑島之際，卻遭逢了難以理解的危機。

在日向一族的聚會中，日足下達了在戰場上由寧次負責統領的指示。由於人選跳過宗家的嫡系，使得日向家的族人們議論紛紛。另一方面，天天邀集所有同期的女性夥伴舉行聚會，與會的雛田從眾人的對話中，回想起自己勤於修練的過往…

木葉忍者村正加緊腳步進行戰爭的準備工作。鬥志高昂的木葉丸也想跟眾人一起上場作戰，為村子立下汗馬功勞。於是他向小櫻和鹿丸等前輩詢問能立下功勞的方法，但是卻沒有人把他當一回事，於是木葉丸作了一個決定…

鳴人在某個港口遇到了來自撫子村的女忍者。過去她們的村長曾經以結婚為賭注向自來也提出挑戰，但這場戰鬥卻沒有分出勝負，於是兩人便約定由彼此的徒弟繼續這場戰鬥，但是得知詳情的鳴人，卻無法接受這種無視雙方心意的擇偶方式。

面對學生的提問，志乃回想起過去自己還是下忍的一段回憶。那是發生在第八小組執行任務之時，因為自己的弱點被敵人掌握而導致任務失敗。當時的牙與雛田為了鼓勵消沉的志乃，約他前往溫泉區一邊療傷一邊鍛鍊近身肉搏戰的實力。

為了即將到來的大戰，天天陪著小李進行強化八門遁甲的修練，但小李卻在跳入瀑布之後遲遲不見人影。當她大聲呼喊小李之際，天天回想起自己過去崇拜綱手大人，為了更接近理想而每天熱衷於修練的往事。

祭利用難得的休假到村子郊外散心。雖然重建工程如火如荼地進行中，但實際上卻還是人手不足。祭在廢墟裡遇到了正在玩耍的孩子們，當他們問起「夥伴」與「朋友」有什麼不同之時，祭不由得露出了一臉苦笑。

井野、丁次、鹿丸以巧妙的默契擺平了孩子們的紛爭。在一旁看到這一幕的萬年下忍小助爺爺，竟誇獎起他們三人的合作默契。並跟三人分享起過去在木葉毀滅行動中，自己因為他們父親的豬鹿蝶陣型而獲救的往事。

不知不覺中差了「村子的英雄」鳴人一大截，這讓牙覺得很不甘心。為了縮短兩人的差距，牙請卡卡西協助自己修練，但是卡卡西卻因有要務在身，於是改為召喚八忍犬出面協助。對於這個作法十分不滿的牙，下定了某個決心。

航程最後的補給地就在眼前，船行至此雖然可以暫時放心，但最近有種連查克拉都能拷貝的變身之術，於是大和還是慎重地提醒大家不可掉以輕心。就在當天晚上，阿凱在半夢半醒之際，竟然看到了本該待在木葉村內的卡卡西。

在鳴人他們進行最後補給的地方，身為土影使者的赤土與黑土遭到了霧忍的攻擊。雖然鳴人與前來迎接的長十郎即時介入，但赤土卻已身受重傷。而策動這次攻擊行動的人，就是人稱「與須賀嶺悲劇事件」的僥存者。