1889년 비행콘테스트에 출전하기 위해 피리의 만국박람회를 찾은 발명을 좋아하는 소년 쟝은 세느강 근처에서 소녀 나디아를 우연히 보고 첫눈에 반한다. 쟝은 나디아에게 친구가 되어 달라고 하지만 나디아의 반응은 차갑다. 그런데 그곳에 나디아가 지닌 보석인 '블루워터'를 노리는 삼인조가 나타난다.

쟝과 나디아는 삼인조한테서 겨우 도망쳤지만 비행기의 고장으로 바다에 불시착한다. 우연히도 정찰 중이던 미국의 전함에 발견되어 도움을 받은 두사람. 포기할 줄 모르고 쫓아오는 그라탱도 전함 앞에서는 무릎을 꿇는다. 하지만 한숨 돌리기도 무섭게 이번에는 의문의 거대바다괴물이 나타나 전함과 격렬한 전투를 시작한다.

의문의 거대바다괴물과 전함의 전투로 바다에 빠지게 된 쟝과 나디아. 그 둘 앞에 또 한 마리의 바다괴물이 나타난다. 하지만 그것은 생물이 아닌 최신 장비로 이루어진 잠수함이었다. 해적을 쫓고 있다는 잠수함 안에서 둘은 에레크트라라고 하는 여성에게 극진한 대접을 받는다.

노틸러스호와 헤어진 쟝과 나디아는 개조해 준 비행기를 타고 프랑스로 향한다. 그런데 도중에 갑자기 공격을 받고 비행기는 가까운 섬에 추락하는데 하필이면 그 섬은 의문의 침략자들에 의해 점령당한 곳이었다. 추락으로 다른 곳에 떨어지게 된 둘은 다시 만나게 되고 침략자들에게 부모를 빼앗긴 소녀 마리와 만난다.

침략자들에게 마리가 잡혀가고 쟝과 나디아는 마리를 구하기 위해서 섬 중심부에 있는 비밀기지에 잠입한다. 둘은 그곳에서 노틸러스호와 싸웠던 잠수함을 목격한다. 잠수함도 의문의 비밀기지도 '네오 아틀란티스'라고 하는 조직에 의해 만들어진 것이었다.

쟝을 구하기 위해 대신 잡힌 나디아. 네오 아틀란티스의 수령인 가고일은 나디아를 공주라 부르며 마리와 킹을 인질로 조직에 협력할 것을 요구한다. 그가 노리는 것은 대체 무엇일까? 한편 쟝은 나디아 일행을 구출하기 위해서 광차를 타고 기지의 중심부로 향한다.

바벨탑의 발사 실험이 진행되고 악당삼인조 그랑디스 일행과 조우한 쟝은 나디아를 구하기 위해서 힘을 합치기로 한다. 성에 잠입한 쟝은 가고일과 대면한다. 가고일은 나디아 일행의 목숨과 맞바꿔 블루워터가 있는 곳을 캐내려는데…

네오 아틀란티스 기지가 붕괴되고 그라탱을 타고 바다로 도망쳐 나온 쟝 일행은 노틸러스호에 구조를 요청하고 네모 선장의 허락 하에 구출된다. 나디아는 불안한 얼굴을 하고 있지만 쟝과 핸슨은 노틸러스호의 과학기술에 반해 기뻐하고 그랑디스는 네모 선장을 보고 첫눈에 반한다. 그리고 네모 선장은 나디아를 처음 보고 놀란다.

네모 선장의 명령으로 각 방을 쓰게 되고 싸움을 하게 된 쟝과 나디아. 한편 노틸러스호는 가고일의 비행선 칼카로돈을 추격하지만 역으로 신형 부유기뢰에 둘러싸이게 된다. 네모 선장을 흠모하는 그랑디스는 수리가 끝난 그라탱으로 기뢰 제거를 나선다.

노틸러스호를 위기에서 구한 그라탱의 활약이 인정되어 그랑디스 일행은 견습 승무원으로서 채용된다. 객원이 된 나디아도 뭔가 도움이 되고 싶어서 선내의 조리장에서 그랑디스를 돕지만 실패만 한다. 한편 쟝은 선내를 헤매다 자기도 모르게 엔진실 안으로 들어가 무언가를 보게 되는데…

생선요리에 질려 불만의 소리가 커지자 네모 선장은 '사냥의 날'을 마련하고 노틸러스는 무인도에 상륙한다. 배 안에서 섬으로 잇달아 나오는 선원들. 네오 아틀란티스를 멸하려는 목적으로 모인 많은 선원의 수를 보고 쟝 일행은 놀란다. 그날 밤 무인도의 해변에서 그랑디스는 나디아에게 자신의 과거를 이야기한다.

새끼사슴을 죽였다는 이유로 크게 화가 난 나디아는 쟝과 싸우게 되고 다른 선원들은 모두 각자의 일로 바빠 누구의 관심도 받지 못하는 마리는 킹과 모험에 나선다. 마리와 킹은 가는 도중 기찻길을 발견해서 놀다가 길을 잃게 된다. 그리고 우연히 섬에 정박해 있는 가피쉬를 목격한다.

가피쉬를 쫓아 다시금 바다로 나가는 노틸러스호. 그런 와중에 마리가 원인 모를 일사병에 걸린다. 그리고 나디아까지 쓰러지게 돼 둘 다 이틀밖에 살지 못한다는 진단을 받는다. 병을 고칠 수 있는 딱 한 가지 방법이 있었는데 리프64라고 불리는 심해에 서식하는 특별한 약초를 구하는 것뿐이었다.

식물마저 전함 내에서 창조해낼 수 있는 노틸러스호의 과학의 힘에 더욱 놀라게 된 쟝과 그와 반대로 반발하는 나디아. 그 와중에 노틸러스호는 가피쉬와의 전투 중에 큰 피해를 입게 된다. 수리를 하기 위해 해상으로 부상을 하지만 위에서 대기하고 있던 미국의 전함의 집중포격을 받고 노틸러스호는…

이 모든 것의 원인이 되는 블루워터를 지닌 자신의 운명에 대해 고민하며 괴로워하는 나디아. 한편 선체수리 중에 기관부에서 새어나온 유독가스에 의해 희생된 승무원들의 묘를 만들기 위해 노틸러스호는 '가라앉힌 사원'이라 불리는 해저유적으로 향한다. 유적에 도착해 장례를 거행하는 승무원들. 그런 와중에 쟝은 무언가를 보게 된다.

아버지의 죽음을 알고 쟝은 노틸러스호의 정식 승무원이 되기 위해 지원하지만 네모 선장에게 거절당하고 크게 낙심하는 쟝. 그 모습을 보고 나디아는 다시 한번 쟝의 비행기로 날고 싶다며 그를 기운을 북돋아준다. 그것을 계기로 쟝은 새 비행기의 설계에 몰두하게 된다.

거듭되는 전투보수로 인해 재료가 부족해진 노틸러스호는 보급을 위해 남극에 있는 비밀기지로 향한다. 그 도중 의문의 물체에 공격을 받는다. 그 정체는 몇억년이나 전의 생물인 거대 앵무조개 노틸러스였다. 노틸러스호는 노틸러스에게 잡혀 끌려가게 된다.

남극대륙의 지하에 있는 비밀기지에 도착한 노틸러스호. 네모 선장은 쟝과 나디아를 데리고 어떤 장소로 향한다. 가는 길에는 아주 오랜 옛날에 멸종한 여러 생물이 얼음으로 보존되어 있는 얼음 박물관이 있었다. 미지의 생명, 자연의 불가사의에 놀라는 쟝과 나디아. 그리고 목적지에는 네모 선장의 벗인 고래 이리온이 있었다.

가고일은 공중전함을 만들어 네모 선장을 쓰러트리기 위해 다시 움직이고 있었다. 한편 발명에 몰두하고 있는 쟝은, 자신의 아이디어로 소형 제트기를 만들어낸다. 하지만 비행 실험은 실패로 끝나고 제트기의 폭발로 인해 노틸러스호는 가피쉬에게 소재를 들켜버린다. 네모 선장에게 크게 혼나는 쟝을 본 나디아는…

가피쉬의 집중포격을 받은 노틸러스호는 역으로 가피쉬를 격침시킨다. 그렇지만 공중전함으로부터 가고일의 신병기 슈퍼캐치광선을 맞고 노틸러스호는 공중으로 끌려올라가게 된다. 이어서 발사된 원자진동파에 의해 선채는 파괴되고 절체절명의 위기에 빠진다. 그때 에레크트라 부선장은 한 제안을 한다.

바닷속으로 침몰하는 노틸러스호. 네모 선장은 승무원을 중앙블록으로 모으고 전투블록을 분리시킨다. 폭발한 전투블록이 가피쉬 부대를 전멸시킨다. 중앙블록만 남은 노틸러스호는 가고일의 손아귀에서 벗어난다. 네모 선장은 선장실에 나디아 일행을 부른다. 선장실을 중앙블록과 분리시켜 나디아 일행만이라도 살리기 위해… 그 후 기관실로 돌아간 네모 선장을 기다리고 있던 것은…

나디아 일행을 태운 선장실은 바닷속을 천천이 나아간다. 침수의 위기를 겨우 모면한 나디아 일행. 선장실은 어떤 해변에 표착하고 그곳에서 마리는 가고일의 마크가 그려진 통조림을 발견한다. 하지만 섬은 벌써 아무도 살고 있지 않은 무인도였다. 나디아는 나쁜 사람이 아무도 없는 이 섬에서 살아가기로 결심한다.

하루가 지나고 나디아는 섬의 이름을 '링컨 섬'이라 하고 표착한 곳은 '캔디 만' 해변을 '나마쟈키 비치'라 이름 붙였다. 게다가 일행들에게 자신은 다시 태어났다고 선언하고 과학문명과 연을 끊고 살아간다며 숲속으로 들어가버렸다. 한편 쟝은 마리와 킹을 데리고 선장실에서 물과 먹을 것 등을 옮기고 움막을 만들며 섬에서 생활해 갈 준비를 한다. 한편 굶주린 나디아는 다른 일행의 통조림을 훔치게 되는데…

쟝과 나디아는 고기를 먹느니 안 먹느니를 가지고 심하게 말다툼을 한다. 나디아는 일방적으로 고기를 안 먹겠다고 고집을 부리고 쟝에게 화만 낸다. 그리고 가고일의 썩은 시금치 통조림을 먹고 배탈이 나고 만다. 쟝은 나디아를 위해 약초를 찾으러 나서고 이상한 버섯을 발견해 엉겁결에 먹어버리는데…

사람은 홀로 살아갈 수 없다는 걸 느끼고 쟝에게 감사함을 가지고 아주 온화해진 나디아. 그 모습을 본 킹은 큰 상처를 받고 동요한다. 그리고 킹은 사이좋게 붙어 있는 쟝과 나디아를 목격하고 결국 가출을 해버린다. 킹을 찾으러 나선 쟝 일행. 그 도중에 쟝은 골짜기에서 떨어지게 되고 그곳에서 광맥을 발견한다.

링컨섬에 엄청난 태풍이 덮친다. 쟝이 힘들게 만든 움막은 날아가고 갖가지의 발명장치도 부숴진다. 킹은 강풍에 휩쓸려 행방불명이 된다.

에어튼이 겁내는 '공포의 대왕'으로부터 도망치는 나디아 일행. 중력이상으로 평소보다 빨리 달릴 수 있고 높이 점프할 수 있지만 지나치게 많이 도망친 바람에 섬을 한 바퀴 돌아버린다. 하지만 '공포의 대왕', 그것은 그라탱이었다. 그 안에서 그랑디스 일행이 나오자 뜻밖의 재회로 기뻐하는 그랑디스 일행과 나디아 일행. 하지만 그 기쁨도 잠시뿐 섬은 다시 떠내려가기 시작한다. 나디아 일행은 이주를 결심한다.

새로운 섬에서의 생활을 시작한 쟝과 나디아는 여전히 끊임없는 말싸움을 그랑디스는 네모 선장을 생각하는 마음이 커지기만 한다. 샌슨과 핸슨은 별일 아닌 것으로 의견대립을 하고 싸우게 된다. 에어튼의 경기로 승부를 내라는 제안을 받아들여 샌슨은 킹을 조련하고 핸슨은 아이언 킹을 만들어 킹 대 아이언 킹으로 경쟁하게 된다.

그라탱의 수리가 끝날 날이 가까워지고 모두의 목적지는 아프리카로 정해진다. 그런데 갑자기 모기가 많이 생기는 바람에 작업은 점점 지연된다. 그런 와중에 에어튼은 그랑디스를 꾀서 그라탱을 타고 와인을 마시러 나간다. 그 사실을 안 샌슨과 핸슨은 격노하고 그라탱 2호를 만들어 뒤쫓아간다. 한편 쟝과 나디아는 이상한 동굴을 발견한다. 그 동굴 안에서 보게 된 것은?

지하에 있는 유적에서 갑자기 벽에 빨려들어간 나디아는 섬 안의 대공동에 떠 있었다. 그것은 위성도시 레드노아. 나디아 앞에는 M78성운의 우주인으로부터 만들어졌다는 의문의 거인이 나타나 240만년 전에 M78성운에서 지구로 온 아틀란티스인의 역사를 이야기하기 시작한다. 나디아는 그곳에서 자신의 출생과 블루워터에 얽힌 비밀을 알게 된다. 한편 쟝은 나디아를 구출하려 하지만…

가라앉기 시작한 섬으로부터 그라탱으로 탈출한 쟝과 그랑디스 일행은 도중에 가고일의 공중전함의 공격을 받고 아프리카의 한 마을에 불시착한다. 나디아는 그곳에서 만난 소년 하마하마에게 첫눈에 반한다. 하마하마가 안내해준 마을에서 나디아는 고향 타르테소스의 이야기를 듣는다. 그리고 그의 다정함에 나디아의 마음은 더욱 들뜬다. 그런 와중에 킹은 마을에서 전해져 내려오는 신비한 약인 빨간 열매의 즙을 마시고 폭주하기 시작한다.

킹을 잡아 보물을 요구하는 것는 그랑디스의 첫사랑이었던 자로 그녀에게서 전재산을 빼앗은 곤잘레스라는 남자였다. 킹을 구출하러 간 그랑디스는 나디아와 같이 잡혀버리고 만다. 남겨진 쟝 일행은 면밀한 작전을 세워 하마하마 그리고 마을 사람들과 같이 구출을 시도하지만 도중에 문제가 생겨버리는데…

실연하여 침울해진 나디아. 쟝은 샌슨으로부터 노래를 만들어 보라는 조언을 듣고 자신의 모든 과학기술을 동원해 새 발명에 착수한다. 그런데 발명에 열중하느라 자신을 상대해주지 않는 쟝에게 짜증이 난 나디아. 그랑디스는 나디아의 마음을 달래준다. 그리고 드디어 쟝은 새로운 발명품 전자동 우쿨렐레를 완성한다. 쟝은 곧바로 나디아 앞에서 노래를 시작하는데…

그라탱이 도착한 나디아의 고향 타르테소스, 그곳은 큰 화산호였다. 뭔가에 홀린 것처럼 호수로 다가가는 나디아. 그러자 호수가 갈라지고 지하유적이 나타난다. 나디아 일행은 그 지하유적에 내려가 블루워터의 힘에 이끌려 지하도를 지나간다. 그곳은 고대 아틀란티스인의 유산 블루노아였다. 자신의 탄생의 비밀을 알게 된 나디아는 짊어진 운명의 무거움에 힘들어 한다.

갑자기 나타난 네오 아틀란티스의 공중전함. 공격으로부터 쟝 일행을 보호하기 위해 나디아는 스스로 포로가 된다. 하지만 가고일은 약속을 무시하고 공격을 개시한다. 아슬아슬하게 도망가는 쟝 일행을 의문의 소형잠수함이 도와준다. 그 소형잠수함에서 나온 것은 에레크트라였다. 그녀의 안내로 도착한 곳에는 녹슬은 철골 같은 물체가 있었다. 그것은 네모 선장의 만능전함 뉴노틸러스호였다.

네오 아틀란티스의 공격으로 소멸됐다고 생각했던 뉴노틸러스호는 아프리카의 대륙의 지하 터널을 사용해 공중전함의 공격을 피하고 있었다. 한편 네오 황제의 힘에 의해 블루워터가 발동되고 레드노아는 완전 부활한다. 네오 황제와 만난 나디아는 그가 어떤 자인지 알게 된다. 그리고 네오 아틀란티스는 세계 각국에 선전포고를 한다.

파리 상공에서 뉴노틸러스호와 레드노아의 전쟁이 시작되었다. 레드노아의 주위는 1억볼트의 전자방어막으로 싸여 있어 내부에 돌입하지 못해 고전을 하게 된다. 겨우 방어막을 뚫고 그 구멍으로 침입한 그라탱은 바벨탑을 파괴하기 위해 돌진한다. 한편 레드노아를 쫓아간 뉴노틸러스호는 우주로 향한다. 하지만 우주에서 바벨의 빛이 발사되어 뉴노틸러스호를 직격한다.

나디아의 오빠 네오는 가고일에 의해 기계화 되어 조종당하고 있었다. 네오와 나디아가 네모 선장을 쏘려고 하는 순간 노틸러스호의 반격이 시작되고 네모 선장은 아슬아슬하게 위기를 모면한다. 한편 기적적으로 자신의 의식을 되찾은 네오는 목숨 걸고 나디아를 세뇌로부터 해방시킨다. 의식을 되찾은 나디아는 가고일에게 반발하고 가고일은 본보기로 에레크트라와 쟝을 죽이려고 한다. 슬픔에 잠긴 나디아는 최후의 결단을 내려야 하게 되는데...