츠나데에게서 제4차 닌자대전의 개시가 가까워 졌다는 말을 듣는 사쿠라. 다가오는 전쟁의 기색을 살피고 있는 쵸지에게 개전이 가까운 것을 말하는 시카마루. 나뭇잎마을의 사람들은 각각 다가올 전쟁을 앞에 두고 지켜야 할 것을 위해 조용히 각오를 다져 간다. 그 무렵, 구름마을에서는 다섯 카케가 모여 향후의 전략을 상담하고 있었다. 전체의 결정인 인주력을 숨기는 조건을 받아들이는 대신 츠나데가 라이카케에게 부탁 한 것은….

"인주력을 숨긴다"라는 전략을 나루토가 알지 못하도록, 나루토에 극비 임무를 주고 여행을 떠나게 하는 츠나데. 예언의 문어를 찾는다는 일에 가슴을 뛰면서, 야마토, 가이, 아오바와 함께 배 여행을 떠나는 나루토 앞에 갑자기 난제가 나타난다. 출항하는 항구의 출구에는 배를 공격하는 괴물이 출현하기 때문에 선원들이 배를 내지 않는 것이라고 한다. 일정을 서두르고 있기 때문에 괴물퇴치를 받아들이는 나루토와 동료들이지만.– 그러는 동안 나루토와 동료들은 과감하게 괴물에게 맞서려고 하는 한 청년을 만난다.

배에 익숙하지 않기 때문에 뱃멀미에 시달리는 나루토, 야마토, 가이, 아오바. 그 중에서도 심한 뱃멀미를 하는 가이 때문에 일행은 일단 가까운 무인도에 배를 대기로 한다. 나루토와 동료들은 이 섬에서 사쿠라, 이노 쵸지와 만나는데. 이 섬에는 약초의 보물창고로 일컬어지는 섬으로 사쿠라들은 츠나데의 지시로 약초를 수집하러 온 것이다. 나루토는 가이가 회복할 때가지 사쿠라들과 함께 약초 채집을 도와주기로 하는데, 가는 곳 마다 있어야 할 약초가 보이지 않는다. 그도 그럴 것이 이미 약초는 베니스라는 작은 나라의 상인 닌자들이 거의 채집한 뒤였기 때문이다. 빈 손으로 마을로 돌아갈 수 없는 사쿠라들이지만, 판매정신이 가득한 상인 닌자들도 또한 보다 많은 약초를 손에 넣으려고 다양한 수단을 구사해온다.

자욱이 끼는 안개 때문에 나루토들이 타는 배는 해상에 붙어 강요했다. 한가한 시간을 주체할 수 없는 일행은 왠지 무서운 이야기하기로 들떠 오르는데, 도깨비와 귀신 이야기가 정말 싫은 나루토는 강한 척 해 보지만 무서워서 견딜 수가 없다. 그런 가운데 안개 속에서 한 척의 배가 나타난다. 나루토는 그 배가 조금 전의 괴담에서 들은 유령선이 아닌가 생각해 무서워하는데, 타고 있던 것은 유령이 아니라, 히샤쿠라는 소년 선원이었다. 하지만 그 정도로 큰 배이면서도 그 배에는 히샤쿠 이외의 승무원이 한 명도 없다. 의심스럽게 생각한 야마토가 그 이유를 물어보는데 .

항해 도중 갑자기 나루토가 타고 있는 배가 포격에 노출된다. 포격은 거대한 전함을 연상시키는 섬에서 날아 온 것으로, 그 격렬한 포격으로 인해 마침내 나루토의 배는 난파하고 만다. 이 섬은 주변의 바다를 해쳐놓는 해적들의 거처였던 것이다. 돈이 되는 것은 고철에서 인간까지 송두리째 빼앗아 떠나려는 해적들. 그 추격에서 탈출하기 위해 야마토가 목둔으로 만들어 낸 즉석 잠수정으로 바닷속으로 향하는 일행은 우연히 발견한 해저 동굴에 일단 몸을 숨기기로 한다. 그곳에서 나루토들은 경악할만한 광경을 보게 되는데. 포악한 해적들에 대해 열을 내는 나루토는 야마토들과 함께 계책을 세워 해적들에게 도전한다.

어디선가 날아온 거대 새가 여전히 뱃멀미에 시달리고 있는 가이를 끌고 간다. 가이를 찾아내기 위해 거대새가 날아간 방향에 있는 섬으로 상륙하는 나루토, 야마토, 아오바. 조속하게 가이의 수색을 시작하려 하는 찰나 세 사람은 한 여성을 발견했다. 이야기를 들으려 말을 걸어보는 아오바. 하지만, 왠지 여자는 도망 치듯 집을 떠나 간다. 무심코 뒤를 쫓은 아오바는 도착한 폐허에 있던 자료에서 이 섬에 숨겨진 무서운 비밀을 알게 된다. 한편, 아오바와 헤어져 다른 방향을 가고 있었다 나루토와 야마토는 차례 차례로 나타나는 거대한 생물과 괴물들을 상대로 악전 고투하고 있었다.

그것은 옛날 가이의 애제자 리가, 필살기인 이연화를 습득해 축하파티를 한 다음날이었다. 너무나도 기쁜 일이라 분위기에 휩싸여 과음을 한 가이는 도중부터의 기억을 잃은 상태였다. 왜인지 전날 저녁에 함께 있던 리도 같은 상황으로 둘은 필사적으로 기억의 끈을 되짚어 간다. 그리고 가이는 막연한 기억 속에서 어느 결론에 도달하는데. 아무래도 자신은 축하를 위해 선택한 가게에서 만취 한 바람에 발광을 하는 추태를 보인 것이다. 어떻게든 스승의 면모를 유지하고 싶은 가이는 리의 기억이 돌아오지 않도록 되는대로 엉터리 수업을 만들어 신경을 분산시킨다.

물과 식량 보급을 하기 위해 나루토가 타고 있는 배는 어느 항구에 들린다. 야마토의 지시로 식량조달에 나선 나루토는 거기서 한 채소팔이와 만나 그 상인이 추천해 주는 대로 버섯을 산다. 그런데 항구에서의 보급을 끝나고 다음의 항해를 나선 배로 터무니 없는 악몽이 닥치는데. 몸 상태가 갑자기 나빠진 야마토의 쓰러짐이 악몽의 시작이었다. 그 후 식량창고에 본 적 없는 독 버섯이 번식하고 음식은커녕 물까지도 침식되어있는 것이 판명되었다. 하지만 머물러 있는 해역의 특수한 해류 탓에 빨리 갈 수도 없고 육지에 들를 수도 없다. 나루토와 동료들의 서바이벌 생활이 시작되었다!?

수 일간 계속되는 폭풍에 농락당하고 있는 나루토와 동료들. 나루토는 환영분신을 동원해 방대한 일들을 정리해가지만 엉망으로 혹사당하고 결국 무시하는 듯한 본체나루토의 태도 때문에 환영분신들의 불만이 한번에 폭발한다. 본체 나루토를 감금하고 처우 개선을 요구하기 위해 반란을 일으킨 것이다. 황급히 그림자 분신을 풀려고 하는 나루토 이지만 왜인지 풀리지 않고 - 어쩔 수없이 야마토, 아오바, 가이 세 상급닌자들에 의해 구출작전이 시작 되는데…

대전을 앞두고 동료들의 생명을 책임지게 된 것을 무겁게 느끼고 있는 시카마루. 시카쿠는 그 생각을 간파한 듯 시카마루를 먼 곳의 임무로 보낸다. 그것은 항로의 도중에 있는 모즈쿠섬에서 나루토들과 합류하여 물자를 보급하는 임무였다. 무사히 목적을 달성하고 섬을 나가려는 일행이지만 갑자기 배는 안개에 싸여 나침반이 이상하게 움직이기 시작한다. 그리고 달려드는 몇 개의 위험- 어떻게 든 넘겨버리고 해역에서 탈출하려고 나루토들 이었지만 배는 같은 장소를 돌기만 하는데. 게다가 이 현상은 환술이 아니었다.

휴우가 일족의 모임에 소집되는 히나타. 당주의 히아시는 모인 사람들에게 제4차 닌자대전을 향한 일족의 체제에 대해 설명한다. 히나다는 너무 어리다는 이유로 전선에서는 네지가 일족을 통솔하도록 지시하는 히아시. 종가의 적자를 뛰어 넘는 인선에 울렁이지만 휴우가 일족들은 뒷전으로 하고 은사 • 쿠레나이를 문병하러 가는 히나타. 배웅하는 네지의 뇌리에는 이삼년간 히나타 함께 한 수업의 날들이 되살아나고 있었다....

오랜만에 바다를 벗어나 육지를 향하는 나루토, 야마토, 가이, 아오바의 앞에 “나뭇잎마을의 우즈마키 나루토”라고 자칭하는 도적이 나타났다. 그러나 진짜의 나루토와 닮은 모습이라고는 찾을 수가 없다. 본인 앞에서 정체가 들켜 자포자기하고 나루토에게 싸움을 거는 도적. 거기에 도적을 쫓고 있다는 닌자가 나타났다. 실은 두 사람이 동료이며 출세를 꿈꾸고 이름을 알리기 위해 곳곳에서 유명인을 사칭하고 잡아들이는 일을 반복하고 있었다. 그런 내막이 있다고는 전혀 알지 못한 나루토들은 나타난 남자에게 도적의 신병을 전달 하고 길을 서두른다. 하지만 뜻밖에 "도적 • 우즈마키 나루토"의 소문이 퍼지고 있어 그 때문에 나루토를 이야기 두 사람은 궁지에 몰리게 된다..

어느 항구에 도착한 나루토는 여자만 있는 닌자 마을인 나데시코 마을의 차기 이장 시즈카와 그 수행원인 토키와와 만난다. 두 사람의 이야기를 들어보면 지라이야의 제자를 찾고 있다고 하는데. 나데시코 마을에서는 이장 될 쿠노이치가 자신과 싸워 이긴 남자를 사위로 맞이하는 풍습이 있고, 수십 년 전에는 지라이야가 선대 이장의 사위 후보 이였던 적도 있었다. 하지만 그때는 대결은 승부가 나지 않았고 둘은 이 승부를 자신들의 제자에게 맡겼다. 스승들이 마음대로 정한 룰에 의해 시즈카와 싸울 것을 강요 받는 나루토. 하지만 서로의 마음을 무시한 사위 선정 방식에 납득이 가지 않고.......

나뭇잎 마을의 닌자 아카데미에서 학생들을 지도하는 시노는 학생의 질문에 대답하기 위해 자신이 아직 하급닌자였을 당시의 이야기를 시작하고 있었다. 언젠가 시노가 속한 제8반은 타켓인 도적닌자를 잡지 직전 이었지만 놓쳐 버린 일이 있었다. 그 원인 중 하나는 시노가 적에게 약점을 잡힌 것 이었다. 낙심한 시노를 걱정하는 키바와 히나타. 그런 셋에게 쿠레나이는 마을의 온천에 다녀오도록 지시한다. 온천에서 상처를 치료하면서 키바, 히나타와 열성적인 수업을 하고 서툴렀던 접근전도에도 대응할 수 있게 된 시노. 그럴 때 시노들이 놓쳤던 적이 가까이 있다는 정보가 들어온다. 그러나 자신의 부족함으로 임무에 실패한 것을 신경 쓰는 시노는 키바나 히나타의 동료로서 싸우는 것에 대해 아직 망설임이 있다.

대전에 대비해 리의 팔문둔갑을 강화하는 수업을 같이 하게 된 텐텐. 텐텐이 날린 금속인형을 들어올리기 위해 리는 폭포에 뛰어들지만 좀처럼 수면으로 부상하지 않는다. "리~!! 빨리 올라 오라오라고" 텐텐은 동료의 힘을 믿고 목청껏 격려한다. 폭포를 바라 보는 텐텐의 뇌리에는 소녀 시대에 그렸던 꿈과 노력과 열혈하게 달려 왔던 지금까지의 나날들이 되살아나고 있었다.

오래간만의 휴가에 마음 편하게 마을의 교외를 산책하는 사이. 부흥이 진행되고 있기는 하지만 아직도 일손이 채워지지 않은 상황을 실감하고 있는데 부서진 건물 사이에서 놀고 있는 아이들과 만나게 된다. 서로 장난치는 아이들의 모습은 어딘가 사쿠라와 나루토의 모습을 연상시켰다. "동료"와 "친구"의 차이를 물어 보는 아이들의 천진난만한 질문에 쓴웃음을 짓는 사이지만.

우연히 맞닥뜨린 아이들의 싸움을 훌륭한 연계로 중지시킨 이노, 쵸지, 시카마루. 그러자 이 장면을 보고 있던 어르신 하급 닌자인 코스케가 셋의 연계를 칭찬한다. 이전 코스케가 위험에 빠졌을 당시 아스마가 이끄는 이노 시카쵸의 연계기술로 도움을 받은 적이 있는 것이었다. 당시를 그리워하는 시카마루들에게 코스케는 나뭇잎마을 붕괴가 한창일 때 코스케이 목숨을 구한 또 하나의 “포메이션 이노 시카쵸”의 이야기를 들려주려 하는데…

어느 사이엔가 마을의 영웅인 나루토와의 차가 크게 벌어져 이를 가는 키바. 그 차를 줄이기 위해 아카마루와 함께 수업에 임하지만 좀처럼 성과가 나오지 않는다. 생각다 못해 지나가던 카카시에게 수업해 주기를 청하는데 공교롭게도 카카시는 업무에 쫓기고 있었다. 그러나 키바의 생각을 알아챈 카카시는 키바의 수업 상대로 팔인견을 불러낸다. 맥빠져하면서도 재빨리 8닌견을 쓰러뜨려 카카시 본인에게 수업을 받을 수 있도록 하려고 분발하는 키바는 팟쿤(パックン)들에게 도전하지만...

최후의 보급지를 앞두고 여행의 끝이 가까워 진 것을 느끼는 나루토들. 여기까지 오면 이제 안심이라고 안도하는 가이와 아오바지만 방심은 금물이라며 주의를 주는 야마토. 소문에는 최근 차크라까지도 카피하는 변화술이 있다고 한다. 마음을 다잡고 망을 보는 가이지만... 그날 밤, 졸고 있던 가이의 앞에 나타난 것은...

물의 나라 영내의 작은 섬에서 최후의 보급을 한 나루토들. 그 무렵 바위에 은신한 아카츠치와 쿠로츠치는 미즈카게 앞으로 된 서한을 지니고 츠치카게의 사자로서 같은 섬에 와 있었다. 하지만 거기에 갑자기 안개분신의 닌자들이 습격해온다. 지나가던 나루토, 마중 나온 쵸주로가 도움을 주지만 동료 중 한 명이 중상을 입고 만다. 이 습격을 꾸민 것은 안개의 상급닌자 간류. 간류는 요스가고개의 비극이라 불리는 어떤 사건의 생존자였다…