Antaeus was generally named as the son of the sea-god Poseidon and the earth-goddess Gaia, a parentage that places him among the giant offspring of Earth and accounts for the secret of his strength. His descent from Gaia is also the source of his invincibility, since contact with his mother, the earth, continually restored his vigor.

He was said to have a wife named Tinjis (or Tinge), a goddess for whom the North African city of Tingis, modern Tangier, was claimed to be named. By a daughter, Iphinoe, who consorted with Heracles, some accounts gave Heracles a son named Palaemon.

Antaeus dwelt in the interior desert of Libya, where he would challenge all who passed through to wrestling matches. He killed those he defeated, and from their skulls he is said to have built or roofed a temple to his father, Poseidon. So long as he remained invincible, his pile of victims continued to grow.

Because he was a son of the Earth, Antaeus could not be overcome while he remained in contact with the ground; whenever he touched his mother Gaia, his strength was renewed. Heracles encountered him during the labour that took him toward the Garden of the Hesperides. Wrestling Antaeus, Heracles found that throwing or pinning the giant only made him stronger, for each fall returned him to the earth. Understanding the secret at last, Heracles seized Antaeus, held him aloft so that he could not touch the ground, and crushed him to death while he hung in the air.

Antaeus is thought to have been incorporated into Greek mythology after the Greek colonization of Cyrenaica in the mid-seventh century BC, which brought Greek settlers into contact with the Libyan and Berber traditions of North Africa.

Local North African traditions long preserved memory of Antaeus and pointed to a burial place for the giant. When the Roman general Quintus Sertorius crossed from Hispania into North Africa, the residents of Tingis told him that the gigantic remains of Antaeus lay within a certain tumulus; when his men dug it open, they reported finding giant bones.

The monument associated with these stories has been linked to the Mzora (Msoura) stone circle, located some fifty kilometers from Tangier, an example of how Libyan and Berber populations folded the mythological figure into their own landscape and cultural memory.

Antaeus appears across Greek and Roman literature. Pindar associated him with a wrestling ground at Irasa, and Lucan, in his epic Pharsalia, has the story of Heracles' victory over Antaeus retold to a Roman audience as a model of strength overcome by cunning. The contest of Antaeus and Heracles was also among the subjects described in the picture-galleries of Philostratus of Lemnos.

The episode became one of the most widely depicted of Heracles' encounters, valued for its dramatic image of the hero lifting his opponent off the ground, and it remained a recurring motif in later art and literature drawing on the classical tradition.