起：冒険の始まり
ネイト（トム・ホランド）は、輸送機に吊るされた状態で目を覚まします。攻撃を受けながらも、何とか機内に這い上がることに成功しますが、赤い車が落ちてきて、一緒に落下してしまいます。
15年前の回想
15年前、ボストンで10歳のネイトは、兄サムからマゼランの航海に使われた世界地図を手に入れたいと話されます。しかし、博物館から地図を盗もうとして捕まってしまいます。サムはネイトに代々伝わる指輪を渡し、「必ず戻る」と告げて逃げます。
現在の冒険
現在、ニューヨークでバーテンダーとして働く青年ネイトは、サリー（マーク・ウォールバーグ）からスカウトされます。サリーはマゼランの地図とサムに会ったことがあると語り、黄金を探す冒険に誘います。ネイトは迷った末に参加を決意し、黄金の十字架をオークションで奪うために向かいます。
オークションとその後
オークション会場には、大富豪モンカーダ（アントニオ・バンデラス）とサリーの元カノ・ブラドック（タティ・ガブリエル）が現れます。ネイトはブレーカーを落とすために裏方に入り、ブラドックの手下に見つかります。サリーの指示で騒ぎを起こし、サリーは十字架を奪います。ネイトとサリーは逃げて空港へ向かいます。
スペインでの探検
スペインに到着したネイトとサリーは、クロエ（ソフィア・アリ）と合流し、日記に書かれた大きな松を探します。教会で鍵穴を探し、地下室に隠された階段を発見します。ネイトとクロエは地下へ、サリーは地上で探索を進めます。ネイトは行き止まりで閉じ込められ、噴水の水が流れ込んできます。サリーが助けに来て、ネイトとクロエは次の部屋へ進みます。
クロエの裏切り
クロエがネイトに銃を向け、地図を渡すように要求します。クロエはサムと組んでいると告げ、ネイトを気絶させ、地図と十字架を奪って立ち去ります。気絶していたネイトはサリーに起こされ、クロエの裏切りを知ります。ネイトは宝探しを続ける決意をします。
モンカーダの飛行機とその後
ネイトとサリーはモンカーダの飛行機にこっそり乗り込みます。機内で、モンカーダが演説中にブラドックが首を切り、自分に従うよう宣言します。クロエはこの事態に気付き逃げ出し、貨物室でネイトとサリーと合流します。貨物室では銃撃戦が始まり、クロエは赤い車に乗り込み、ネイトと共に落下します。二人は貨物の上に乗り、付いたパラシュートでピンチを切り抜け、近くの島に上陸します。
フィリピンでの結末
ブラドックは手下と共にフィリピンに到着します。ネイトとクロエはホテルで休息を取り、ネイトは兄サムとの思い出を元に、十字架がコンパスになることを発見します。ネイトは正確な場所を地図に記し、クロエが出発する前に嘘の場所を記しておきます。クロエが偽の地図を持って出発すると、ネイトは正しい場所へ向かいます。
黄金と結末
ネイトとサリーは、洞窟の奥で2隻の帆船を見つけますが、ブラドックとその手下たちが現れます。ブラドックは船ごと運ぶためにヘリコプターを用意していました。ネイトとサリーは船から脱出し、手下たちを倒してヘリコプターを乗っ取り、逃げようとします。ブラドックは帆船のイカリを使ってヘリコプターを落とそうとします。ネイトは黄金を諦めてリュックをブラドックにぶつけ、ブラドックは海に落ち、その上に帆船が落ちます。
沈みゆく帆船を見たネイトは「後で取りに来よう」と言いますが、サリーは国有財産になるため無理だと説明します。二人はヘリで逃げる途中で、クロエが関係ない場所で探しているのを見つけ、クロエは騙されたことに気付きます。ネイトとサリーは笑いながら去ります。
最後に、サリーが収穫なしと嘆く中、ネイトはポケットに入っていた小さな黄金の粒を渡し、サリーは感激します。