ビクトリア女王時代。英国占領下のボルネオ北西部の回教国民はギロンク卿(レオ・アンコリス)に隷属を強いられていた。国王は幽閉され、王妃ら一族は殺されていたが王子サンドカン(スティーヴ・リーヴス)は逮捕を免がれ、友人のポルトガル人やヤネス(アンドレア・ボジック)や部下とともに孤島に避難した。国民の間にサンドカンに対する期待の強いのを知った卿は、彼をおびき出すために、国王を殺すとふれさせ、サンドカンはその計略にのって部下数名とともに本土に渡った。だが要塞は厳重な警戒で、潜入は不可能だった。そのとき、要塞への使者が通りかかった。ヤネスが使者になりすまし、卿にサンドカンは死んだと報告、相手が非常態勢を解いたので、サンドカンらは一挙に侵入、卿をとり逃したが、姫のメアリー(ジュヌヴィエーヴ・グラ)を人質にした。島に帰る途中、待ち伏せていた卿の一隊と激戦を交え、ヤネスは傷ついた。やむなく内陸を横切るという、大湿地帯、猛獣地帯を通る、苦難の道を逃れた。途中、首狩り族に捕えられ、いけにえに供される寸前に王と盟友だったルブアン族に助けられ、やっと島に辿り着いた。またも敵兵の待ち伏せにあい包囲された。サンドカンは無益の抵抗を止め、部下の自由を条件に降服した。だが卿は前言を翻し、一同を縛り首にすることにした。サンドカンとヤネスは猿の力をかりて脱獄、部下らと暴れまくった。そしてダイアク族の来援で、ついに勝利をかちえた。