The story starts off with a prehistoric ice-world-ish tribe having an unexpected visitor: a blue-eyed girl named Evolet, who happens to be the only survivor of 'four-legged demons' (later revealed to be men on horse-back) ravaging her village. She stays in the village, and she catches the eye of a young boy, D'leh.
D'leh's father is seen later to be leaving the village, going 'over the mountains' for a reason to be revealed later in the movie. He passes his white spear, the symbol for the best hunter of the tribe, to his friend Tic'Tic, who keeps the reason secret from everyone else. As D'leh grows up as a young man, he is bullied and ridiculed for being the son of a coward. Seeking to gain back honor, he joins in the annual mammoth hunt, to claim the white spear and his beloved Evolet. During the mammoth hunt, they funnel the largest one in a bottleneck but it manages to tear free from the nets. Several hunters hang on, with D'leh and his main rival Ka'Ren hanging on last. D'leh wants to let go, but his hand is stuck. As the mammoth frees itself, it's cornered at a cliff. D'leh plants his spear in defense and the mammoth accidentally falls on it; D'leh is credited with killing the mammoth when in fact, he didn't. Tic'Tic is reluctant to award the spear to D'leh but D'leh claims it anyway. Later on, he gives it up out of honesty.
That winter, the horsemen from over the mountains ravage their village, taking men and women for slaves, leaving the rest to die. D'leh sees Evolet being abducted and is determined to save her. Tic'Tic, Ka'Ren, and a young boy named Ba'ku comes along. Along the way, the scenery changes from icy cold mountains, to green forests, and finally to a desert, which suggests a trek from Europe to Africa. In the forests, D'leh manages to free his tribesmen before falling under attack from giant predatory birds. Only D'leh and Tic'Tic escape capture. They follow the horsemen into the desert, but while hunting for deer, D'leh falls into a pit, where he is stuck with a trapped saber-toothed tiger. D'leh plans to kill the drowning tiger, but out of mercy, he saves it. The tiger jumps out of the pit while D'leh uses the fallen timbers to climb out.
In their trek, they come across an African tribe. Suddenly, the saber-toothed tiger (called by the Africans as Spear Tooth) jumps in and protects D'leh and Tic'Tic. This convinces the Africans that D'leh is The Hunter, he who communicates with the Spear Tooth and is the one to save the slaves in the Mountain of the Gods. With this, a call to arms is issued and D'leh gathers an army of elite African warriors. D'leh finds out that the Africans can speak his language because his father went here before, in search of food for his people as he doesn't rely on waiting for mammoths to come annually. The Hunter, meanwhile, is said to be the only one who can kill the Almighty One (the Pharaoh).
They all arrive at the Mountain of the Gods, which is revealed to be Ancient Egypt. The priests fear Evolet, as the scars on her hands are in the likeness of The Hunter (if you know your constellations, it's actually Orion). The mark of The Hunter is said to bring the death of the Almighty. Slaves are constructing the pyramids with the help of thousands of slaves, and amazingly, mammoths. D'leh formulates a plan of attack when he infiltrates the slave camp and tells them on how he plans to cause an uprising. As he is discovered, he runs back to the camp. 3 Egyptian warriors follow and are about to run off with their spy report when Tic'Tic (who guards D'leh's back all the time) confronts them. He kills 2 of them, and does not see the last wounded one. He is stabbed and dies, with the final words to D'leh, "Be as your father".
The next day, D'leh and his warriors dress as slaves and infiltrate the workforce. D'leh and Ka'Ren see the mammoths pulling the huge blocks of stones and decide to do what they do best; encouraging a mad stampede among the giant beasts. D'leh provokes the matriarch while Ka'Ren holds off the Egyptians. Ka'Ren is cut down, but the stampede succeeds, killing many Egyptians. The other slaves see the revolt and join in. As the priests see this, they take Evolet and threaten to rip her apart if D'leh doesn't stop. D'leh refuses because the slaves are not to be freed. He throws his spear at the Pharaoh, killing him, and leaving everyone wondering. Meanwhile, the leader of the horsemen kidnaps Evolet on horse-back. Evolet inflicts a mortal wound on him with an arrow and they fall. As Evolet and D'leh run toward each other, the horseman shoots at her, killing her out of spite. D'leh spears him, but it's too late. Evolet dies.
Old Mother, the tribe's prophet, gives up her last breath to Evolet, restoring her life. As D'leh and his remaining tribesmen go home, their African friends give them seeds to plant. The scene ends with D'leh in wonderment at how fast the crops are growing.