BGMにロックバラードが流れるなか、ヨオがカッパドキアにそびえ立つ岩々の周辺をジョギングしている場面から映画は幕を開ける。
すぐ近くの村では、見るからに原始的な女性カラとその付き人パグが狩りをしていた。突如、彼らはトリケラトプス[3]に襲われるのだが、どこからともなく現れたヨオがトリケラトプスの頭をかち割って2人を救う。ヨオはカラたちの暮らす村の人々に迎え入れられ宴が催された。しかしその夜、青い肌をした原始人の一群が村を襲う。ヨオとパグだけが逃げおおせ、ヨオはさらわれたカラをすぐさま助け出すことを誓うのだった。2人は青い原始人たちの跡を追っていき、ねぐらを見つけることに成功する。ヨオは岩陰で大きなバットを振るい、原始人の1人を殺すと、死体とバットをハンググライダーのように使い合わせてねぐらへと突撃。カラを無事助け出し、押し寄せてくる原始人たちを前に退散していった。
こうして幾多の冒険を経ながらも、物語の本筋はヨオが自らのルーツを探ろうとするところにあり、最終的には嵐が吹き荒れるひとつの島にたどり着く。そこでヨオの両親は核兵器による大量虐殺から生き残ったわずかな群衆の一員だったことを知る。そして帝王と呼ばれる悪の男がアンドロイドの軍隊とともに残る核技術を支配しているのだった。
