An unspecified moment in prehistory. Akhoba, the Rock tribe chieftain, leads a hunting party through the volcanic wasteland. He is accompanied by his sons, Tumak and Sakana. When a wild boar falls into a trap, Tumak kills the animal and claims a tusk as a trophy. The hunters drag the carcass back to their cave, leaving an injured member of their party behind to be eaten by vultures.
That night, the Rock tribe feasts on the roasted boar. The strongest and most aggressive members of the tribe take the majority of the food, leaving just scraps for the elderly and the very young. Akhoba steals Tumak's share of the meat. They fight, and Tumak is hurt: he falls off a cliff, leaving Akhoba as the victor. Sakana comes forward to claim Tumak's woman, Nupondi, as his own.
A bush breaks Tumak's fall. He regains consciousness and sets off into the desert, exiled from his tribe. He is attacked by a giant lizard and hides in a cave, where he finds dozens of skulls mounted on wooden stakes.
As he continues into the desert, Tumak comes across huge sets of animal tracks. They belong to a brontosaur and a giant tarantula. Delirious from hunger and thirst, he staggers onwards. He reaches a beach and collapses on the sand.
On the beach, the Shell tribe women are fishing with spears. One of the women, Loana, spots Tumak and goes to help him. At that moment, a giant turtle approaches, intent on eating everyone. The turtle is driven back into the sea by the spears of the Shell people.
Tumak is taken to the village of the Shell tribe, where Loana nurses him back to health. They are a peaceful people who have learned to cooperate with one another, and have developed rudimentary forms of art and agriculture.
While hunting goats, Akhoba slips and ends up hanging from the edge of a cliff. He calls for Sakana, who instead of helping his father, stamps on him and makes him fall. Sakana declares himself leader of the Rock tribe.
Back at the cave, a wild celebration takes place to celebrate Sakana's succession to the leadership. At the height of the revels, Akhoba drags himself into the cave. He is partially paralysed and blind in one eye.
The Shell tribe treat Tumak somewhat warily. Ahot, one of their hunters, shows him how to make spears, something that the Rock tribe has yet to develop. In return, Tumak shows the children how to gather fruit from the trees more efficiently.
An allosaur attacks the Shell tribe's village and threatens the children that Tumak has just befriended. He rescues a little girl and kills the creature. Soon afterwards, he steals Ahot's spear. They fight, and once more Tumak is exiled from society. Loana decides to accompany him.
Tumak and Loana pass once more through the cave filled with skulls. They hide when a group of cannibalistic ape-men appear. The ape-men kill one of their number, stick the head on a stake and proceed to eat the body. Tumak and Loan make their escape whilst the creatures sleep.
They continue through the desert, but are trapped by a fight between a triceratops and a ceratosaur. Loana avoids the dinosaurs, but is captured by Sakana and his hunters. Tumak fights Sakana and wounds him with his spear. He and Loana return to the Rock tribe in triumph, whilst Sakana and his followers flee.
Nupondi is jealous of Loana's closeness to Tumak. She attacks her but is defeated. Loana refuses to follow the Rock tribe's tradition of killing a vanquished foe, and spares Nupondi's life.
Loana teaches the Rock people how to swim. As they arrive at the waterhole, a pterosaur scoops up Loana and takes her to its nest as a meal for its babies. A rival pterosaur attacks and Loana is dropped into the sea, where the Shell tribe rescues her.
Tumak is reunited with Loana, who is brought to him by a party from the Shell tribe. Sakana launches a surprise attack whilst a nearby volcano erupts. Tumak kills Sakana and escapes from the devastation with Loana and a mixed group of Rock and Shell survivors.
