Eurystheus was born into one of the most illustrious families in Greek mythology. His father was Sthenelus, the son of Perseus, the hero who had slain the Gorgon Medusa, a creature whose face turned all who looked upon it to stone, and who had rescued Andromeda from a sea monster by turning it to stone with the Gorgon's severed head. His mother was Nicippe, a daughter of Pelops, the legendary king of Pisa whose chariot race won him a bride and whose descendants shaped the history of Greece. Eurystheus was thus a great-grandson of Zeus through Perseus, and his cousin was Heracles, the son of Zeus and Alcmene, who was also a great-grandson of Perseus through a different line. The two men were of the same generation, born to granddaughters of Perseus, and both had a claim to the throne of Mycenae.

The contest between them began before either was born. Zeus, the king of the gods, had boasted that the next descendant of Perseus to be born would rule over all Greece. Hera, Zeus's wife, who hated Heracles because he was the living proof of her husband's infidelity, devised a trick. She delayed the birth of Alcmene, who was pregnant with Heracles, by seven days, and at the same time she hastened the birth of Nicippe, who was pregnant with Eurystheus. The result was that Eurystheus was born first, and by the letter of Zeus's promise he became the rightful king. Heracles was born a week later, and though he was the stronger and the greater man by every measure, he was bound by the will of the gods to serve his weaker cousin. The poet Homer, in the Iliad, records Hera's own words on this matter: she boasts that she had made Eurystheus king over the Argives, and that she had sent Madness to afflict Heracles so that he would serve his cousin, even though Heracles was the stronger and the better man.

The Twelve Labours began after Heracles, in a fit of madness sent by Hera, killed his wife Megara and their children. In his grief, Heracles went to the oracle at Delphi, where the god Apollo told him that he must serve Eurystheus for ten years and perform whatever labours the king demanded. Eurystheus, who was sickly and cowardly, seized the opportunity to destroy his stronger cousin. He assigned Heracles a series of tasks that seemed impossible: to slay the Nemean Lion, whose hide was impervious to weapons; to slay the Lernaean Hydra, a nine-headed serpent that grew two heads for every one cut off; to capture the Ceryneian Hind, a deer with golden antlers sacred to Artemis; to capture the Erymanthian Boar; to clean the Augean Stables in a single day; to drive away the Stymphalian Birds; to capture the Cretan Bull; to steal the Mares of Diomedes; to fetch the belt of Hippolyta, queen of the Amazons; to fetch the cattle of Geryon; to fetch the golden apples of the Hesperides; and finally to capture Cerberus, the three-headed dog who guarded the gates of the underworld. Each task was meant to kill Heracles, and each one he completed through strength, cunning, and the help of the gods.

Eurystheus's cowardice became legendary. When Heracles returned with the Erymanthian Boar, the king was so frightened that he hid in a half-buried storage jar, a pithos, begging the hero to get rid of the beast. The image of the king cowering in a jar while the hero stood above him with a living monster became one of the most enduring visual motifs of Greek art, painted on vases and carved in stone across the Greek world. When Heracles completed the first ten labours, Eurystheus tried to cheat him by declaring that two of them did not count: the slaying of the Hydra, because Heracles' nephew Iolaus had helped him burn the stumps, and the cleaning of the Augean Stables, because Heracles had accepted payment from King Augeas. This forced Heracles to perform two additional labours, bringing the total to twelve. The mythographer Apollodorus records this detail, and it has become the standard version of the story.

After Heracles died and was taken to Olympus as a god, Eurystheus turned his hatred upon the hero's children, the Heracleidae. He feared that they would come to claim the throne of Mycenae, and he pursued them across Greece, trying to exterminate them. The children fled to Athens, where the Athenian king refused to surrender them. Eurystheus raised an army and marched on Athens, but the Heracleidae, led by Iolaus and supported by the Athenians, met him in battle. Eurystheus was killed, and in the most brutal detail of the story, recorded by the tragedian Euripides in his play Heracleidae, his head was severed from his body. Alcmene, Heracles' mother, took the severed head and gouged out its eyes with weaving pins, a final act of vengeance for the torment her son had endured. After Eurystheus's death, his uncles Atreus and Thyestes, the sons of Pelops, seized the throne of Mycenae, and the curse of the house of Pelops continued in a new generation of bloodshed.