今から15年前、北大西洋上で八代グループの貨物船・第一八代丸が沈没する事故があった。犠牲者は船長の沖田と三等航海士の2人だけだったが、事故の裏には何かありそうな気配が…。また半月前、八代造船の設計技師・八代英人が車を運転中に心臓マヒを起こして崖から転落。自分が設計チームを率いた八代グループ自慢の最新豪華客船アフロディーテ号の処女航海姿を見ることなく、世を去ってしまった。

そして、現在。太平洋を処女航海中のアフロディーテ号の船上に、コナンや蘭たちの姿があった。もとは園子の両親が、八代グループ会長の八代延太郎に招待されていたのだが、出席できないため、代わりに少年探偵団や阿笠博士も含めて一緒に誘ってくれたのだ。メインダイニングでディナーを楽しもうとするコナンたちのところに、シナリオライターの日下ひろなりがやってきた。小五郎のファンだと言ってぜひ同席させて欲しいと。日下は、豪華客船を舞台にしたドラマを企画していると言う。日下に紹介されたアフロディーテ号の設計チームの一員・秋吉美波子と一緒に楽しい食事を始めるコナンたち。ただし小五郎は、美波子が、別居中の妻、妃英理に似ているため、最初はイマイチのりが悪かった。だがアルコールが入るにつれ絶好調に。一方、日下は途中で気分が悪くなり、部屋に帰ると席を立つ…だが日下が向かった先は！？

ディナーが終わり部屋に帰った少年探偵団の皆は、空手の関東大会で優勝した蘭のために、貝殻で金メダルを作ってプレゼントすることに。翌朝、蘭を驚かせるため彼女のウインドブレーカーのポケットにこっそり金メダルを入れておくことにする。その頃、延太郎のもとに「15年前の秘密を知っています」と書かれた手紙が届く。延太郎には心あたりがありそうだが、貨物船沈没事故と何か関係が…！？

一方コナンたちは、皆でかくれんぼをすることに。園子と灰原がオニになって皆を探す。コナン、探偵団の皆はすぐに見つかるが、蘭だけはなかなか見つからなかった。園子が言うには、蘭はまるで忍者のようにとんでもないところに隠れるらしい。引き続き園子が捜しに行くが、その途中で園子が…！？その頃、小五郎はパーティーで知り合った麗姉妹の部屋に向かっていた。途中、廊下でウインドブレーカーのフードをすっぽりかぶった人物とすれ違う。

そしてかくれんぼのタイムアップ。見事逃げ切った蘭が現れ、コナンに「ずっとサッカーボールを蹴っていたでしょ」と言う。蘭はいったいどこに隠れていたのか？探偵団の皆は、それよりも金メダルに気付かない蘭にがっかり。それにしても、かくれんぼが終わったのに園子が帰ってこないため、探偵バッジで連絡をとってみると…。

バッジの向こうから園子の悲鳴が！！園子は、どこかに閉じ込められていた！！コナンはまだ知らなかった。この時すでに船に乗り込んだ犯人による恐ろしい陰謀が始まっていたのだ…！！

園子の言葉を手がかりにしたコナンたちの必死の捜索で、彼女を無事発見することに成功！園子は地下のマリーナで、何者かに襲われたと言う。コナンと小五郎がマリーナに行ってみると、そこには延太郎の鉄扇が落ちていた。事情を聞きに延太郎の部屋を訪れたところ、そこには刺殺された女性の遺体が。遺体の主は延太郎の娘で八代客船社長の貴江だった。小五郎は、麗姉妹の部屋に行く途中、貴江社長の部屋から出て来た不審な人物を思い出す…警視庁捜査一課の目暮警部たちがヘリで駆けつけ、本格的な捜査が始まった。鑑識の調べで、貴江社長ばかりか、会長の延太郎も何者かに海に落とされたものと推測された。立て続けに起きた2つの事件の犯人は…？

犯行が可能なのは八代親子のスケジュールを知る人間だけ。だがそれを知っていたのは、2人の世話係をしていたパーサー・辻本夏帆だけのはず…犯人は一体どうやって2人のスケジュールを知ったのか？

一方、八代英人の事故を再捜査していた佐藤刑事は、事故車両の中から怪しい痕跡を発見！事故ではなく殺人事件だった可能性が浮上する。犯人が仕組んだ驚きの殺害方法とは…！？一連の事件が同一犯の仕業だとすると、犯行の動機はおそらく15年前の事故に絡んで八代財閥に恨みを持つ者に違いない。コナンは犯人の目星を付けるが、決め手となる証拠がなかった…。

そしてウェルカムパーティーが始まり、船長たちメインクルーが乗客たちに挨拶を。だが船内で八代親子が殺されたことを知った乗客たちは騒ぎ出してしまう。それをしずめたのが、小五郎の一声！マイクを片手に、自信たっぷりに推理を披露し始める！！小五郎が犯人だと指摘したのは、なんと…！？

あまりのとんちんかんな推理の内容に、船内は再び騒然とし始めるが、あとを引き継いだのは、阿笠博士の声を借りたコナン！！だが、ついさっきまで決め手となる証拠がなかったはず…！？コナンの推理と犯人のトリックが激突し、全てに決着が！？しかし、まだ終わっていなかった！！犯人の陰謀は、全ての乗員乗客をも巻き込む、巨大な罠を作り上げていたのだ！！コナン、そして小五郎、2人の名探偵が犯人に挑む！！だが2人の知らないところで、蘭にも危機が迫っていた！！はたして全員無事に生還できるのか！？コナン映画史上初の二重サスペンスの結末は…！？