東京で強盗事件が発生。佐藤刑事は車の助手席に高木刑事を乗せ、車で逃走する強盗犯２人を追跡する。そして、激しいカーチェイスの末、佐藤に追い詰められた強盗犯の車は横転。強盗犯は「神海島」「ジョリーロジャー」という謎の言葉を残して意識を失う…。
　日売新聞のパズルで賞金を手にした小五郎はバカンスのため、コナン、蘭、園子、阿笠博士、少年探偵団、灰原を連れて神海島を訪れる。小五郎はホテルにチェックインしようとするが、手違いで予約が取れていない事が判明。観光課の岩永城児（いわながじょうじ）に代わりの宿に案内してもらう事に。この時、コナンらはガラの悪い男性３人組と遭遇。コナンは外見の特徴から３人がトレジャーハンターだと推理する。この後、コナンらは神海島の海底に財宝が眠っている事を伝えるポスターに気付く。
　宿に向かう途中、岩永は２週間前に海底宮殿で銀の食器が見つかった事を小五郎らに教える。神海島の近くには頼親島という小さな無人島があり、そこから東へ200メートルほど行った海底に巨大な建造物が沈んでいるという。神海島付近に古代遺跡が沈んでいると話題になり始めたのが約10年前。頼親島は今より海上に突き出ていたが300年前の地震で海に沈み、今の形になったという。
そして一行は宿泊する民宿に到着。だが、主人の美馬和男（みまかずお）の無愛想な態度に小五郎は気を悪くする。この後、コナンと少年探偵団、灰原は宝探しゲーム、蘭と園子はダイビングに挑戦する事に。早速、蘭と園子は馬淵千夏（まぶちちなつ）がオーナーのダイビングショップ「グロット」を訪ねる。蘭らがインストラクターの山口喜美子（やまぐちきみこ）と話していると、ホテルにいたトレジャーハンターたちが店の奥から出てくる。彼らはエアーコンプレッサーを借りていったという。
　この後、馬淵は刑務所を脱獄したアンという女海賊が島に宝を隠した話を蘭らに明かす。その頃、コナンらも観光館の展示室でアンのVTRを観賞。海底宮殿で発見されたカットラスという刀とピストルは、刻まれたイニシャルから1730年頃に活躍した女海賊、アン・ボニーとメアリ・リードのものと考えられ、２人はジャック・カラムという船長の仲間だったという。バハマの監獄を脱走したアンは海賊として活躍しながらメアリの脱獄を待っていたという説とも一致する事から２人が奪った宝物を神海島に隠した可能性は高いらしい。コナンと灰原は話を聞きながら展示されたカットラスとピストルも見学する。
　そして、島の説明を聞き終えたコナンらは宝探しゲームを開始。岩永は地図の中の５ヵ所のポイントで数字のスタンプを捺し、謎を解いていくというルールを説明する。各ポイントにはスタンプと宝箱があり、次のポイントのヒントカードが入っているという。最初のポイントは展示室にあり、ヒントカードには「夕陽が落ちずとも海賊はかがやく」と書かれていた。宝物のありかがわかったら特別なプレゼントが貰えると聞いた元太らは気合いを入れる。岩永は問題を全て自分考えた事を明かした後、レンタル自転車をコナンらに貸し出す。
　蘭と園子は山口と共に海に潜り、海底遺跡を見つける。だが、その直後に３人はサメに遭遇し、トレジャーハンターの１人がサメに襲われる場面を目撃する。その頃、コナンらはヒントを頼りに島の最西端へ。コナンはヒントを解き、海ホタルが海面を浮遊する近くで宝箱を発見。ヒントカードには「痩せた海賊は笑う」と書かれていた。この後、灰原は血だらけのウエットスーツ姿の人が運ばれる姿を見かける。コナンは蘭の事を心配して灰原と一緒に病院へ向かう。
　蘭の無事を確認した後、１人だけサメに襲われた事が引っかかったコナンはウエットスーツを調べ、魚の血が付着したビニール袋を発見。何者かがこのビニール袋をBCジャケット（水中で浮力調整する上着）に仕込んだのだ。これは事故ではなく殺人事件だった。灰原にビニール袋の存在に気付くように仕向けられた小五郎はビニール袋の事を皆に伝え、殺人事件だと発表する。
コナンは灰原と共にBCジャケットが細工されたと思われる「グロット」へ。灰原はコナンに頼まれ、店の裏で発見した靴の跡を携帯で撮影する。さらにコナンは馬淵に「グロット」の防犯について確認。馬淵によれば、店にはカギをかけないため、誰でも忍び込んで細工する事は可能だという。この後、コナンは宝探しゲームを続ける元太らに呼び出され、吊り橋の所で合流する事に。コナンは吊り橋に向かうが、土砂崩れで道が塞がっていたため、偶然通り掛かった岩波に別の道を教わる。
　元太らはコナンの到着を待たずに吊り橋を渡り始め、光彦と歩美は渡りきった所に看板を発見。そこには「体重が40キロ以上の人の通行を禁ずる！」と記されていた。看板の事を知らされた元太は45キロもあり、吊り橋の途中で立ち止まって泣き出してしまう。この後、光彦と歩美は宝箱を発見。ヒントカードには「海賊は泣かない」と書かれていた。そこにコナンがやってくる。光彦が状況を伝えるとコナンはヒントの意味を分析。そして、コナンは40キロ以上の人でも吊り橋を渡れる事を元太に伝える。
　夕方、目暮警部や佐藤、高木、白鳥刑事がヘリコプターに乗って神海島に到着。目暮らはトレジャーハンター、伊豆山太郎（いずやまたろう）と松本光次（まつもとみつし）の事情聴取を開始する。佐藤は昨夜の強盗犯が伊豆山と松本の仲間だと自供した事を伝えるが、松本らは証拠がないとシラを切る。そして、高木は帰ろうとする松本からマッチを借り、指紋の採取に成功する。
　夕食後、元太らは「海賊は泣かない」というヒントの意味を解こうと相談。すると、美馬が「海賊は泣く」なら知っていると言い出し、コナンらをその場所まで案内する。美馬が案内したのは泣き砂の海岸。コナンはその海岸の砂が泣かない場所に気付き、「海賊の魂は天に昇る」という新たなヒントカードを見つける。その時、コナンは「グロット」で密会する馬淵と松本の姿を目撃する。コナンは「グロット」に様子を見に行くが、松本は車に乗って店を後にする。
　この後、高木は採取した指紋を鑑識に送信。その時、駐在所の非常ベルが激しく鳴り響く。これは観光館で何かあった事を知らせる非常ベルで、目暮らは観光館へと急ぐ。その頃、松本を追跡していたコナンが観光館近くの道を通ると、ちょうど松本と伊豆山が車に乗り込もうとしていた。そんな松本らに向かって何者かがライフルを発砲。松本らは撃たれながらもその場を立ち去る。
　コナンは何者かが発砲した場所へ行き、薬きょう２個を見つけ、地面に残された何かの跡も携帯で撮影する。飲み屋で飲んでいた小五郎は外が騒々しい事に気付いて外へ出て、自転車で通りかかった岩波を呼び止める。岩波は観光館の展示室に泥棒が入った事を教える。すると小五郎は自転車を奪い、岩波を後ろに乗せて観光館へ向かう。展示室から盗まれたのはカットラスとピストルで、岩波はこの２つが海底宮殿で発見された本物の宝だと告白。カットラスはアン・ボニー、ピストルはメアリ・リードのモノだという。
　この後、駐在所の警官が指紋照合の結果を持ってきて、松岡らが国際指名手配犯だと判明。松岡らは世界各地の遺跡、博物館から美術品、出土品などを強盗、及び殺人の前科がある大物だった。岩波は２人がアンとメアリの宝を狙っていると推理。盗まれたカットラスとピストルが証拠だという。話を聞いたコナンは何やら考えを巡らせる。そして、コナンは小五郎のシャツから何かの匂いを嗅ぎ取り、シャツに何かが付着している事にも気付く。コナンは事件の真相に徐々に近づいていた…。