The game begins with the new Turok, Joshua Fireseed appearing through a portal to face a blue-skinned woman named Adon.

She explains he has been called by the Elders of the Lost Land, the Lazarus Concordance, to defeat a powerful alien entity called the Primagen, a creature imprisoned long ago in the wreckage of his spacecraft after attempting to conquer the Lost Land.

The Primagen was sealed in the ruined craft by five devices called Energy Totems which he now attempts to destroy with his army of creatures from several different races.

In the process Turok must defeat the Primagen's armies and acquire ancient magical powers from the Talisman chambers, eventually leading to Turok facing the Primagen himself.