Andromeda was born into the royal house of Aethiopia, the kingdom that the Greeks believed lay at the southern edge of the world, where the sun burned closest to the earth. Her father was Cepheus, a king of ancient and noble line, and her mother was Cassiopeia, a queen of extraordinary pride. The kingdom was rich and the palace splendid, but Cassiopeia could not resist comparing her own beauty to that of the immortals. One day she declared, or perhaps boasted of her daughter's beauty, that she and Andromeda were more lovely than the Nereids, the fifty sea-nymphs who attended the god Poseidon, the ruler of the oceans and earthquakes. The Nereids, hearing this insult, went to their father Nereus, the old man of the sea, and to Poseidon himself, and demanded vengeance for a mortal's hubris. Poseidon, enraged, sent a flood to drown the coast of Aethiopia and unleashed Cetus, a sea monster of immense size that rose from the depths and began to devour everything in its path.

King Cepheus, desperate to save his kingdom, travelled to the oracle of Ammon, a prophetic shrine in the Libyan desert, though some say he consulted the oracle at Delphi instead. The answer was cruel and absolute: the land would know no peace until Andromeda was offered to the monster as a sacrifice. Cepheus and Cassiopeia, weeping, had no choice. Their subjects demanded the sacrifice, and the king's duty to his people outweighed his love for his child. Andromeda was stripped of her royal garments, adorned only with jewels, and led to a rock by the sea at Jaffa on the Levantine coast. Heavy chains were fastened around her wrists and ankles, and she was left there to await the monster, the waves lapping at her feet and the sky empty above her.

Perseus, the demigod son of Zeus and the princess Danae, was flying homeward on the winged sandals he had received from the god Hermes, the messenger of the gods. He had just completed his greatest feat: he had entered the lair of the Gorgons, three sisters so terrible that one look at their faces turned any living creature to stone, and he had cut off the head of Medusa, the only mortal of the three, using a sickle of adamant given to him by the goddess Athena. He carried the severed head in a special wallet, and the blood that dripped from it was so potent that even in death it could work miracles. As he flew over the coast of Aethiopia, he saw Andromeda chained to the rock and was struck by her beauty. He descended and asked her name and her story, and she told him, weeping, of her mother's boast and the oracle's command. Perseus fell in love at once and went to her parents with an offer: he would kill the monster and save their daughter, but only if they gave him Andromeda's hand in marriage. Cepheus and Cassiopeia agreed gladly, promising him their kingdom as a dowry.

The sea monster rose from the waves with a roar that shook the shore. In some accounts, Perseus drew his sword, a blade forged by the gods, and hacked at the creature's body, dodging its jaws and stabbing again and again until the waters ran red and the beast sank beneath the surface. In other accounts, Perseus held up the severed head of Medusa, and the moment Cetus looked upon that terrible face, the monster turned to solid stone in an instant, frozen forever in the act of rising from the sea. Either way, Andromeda was free. Perseus broke her chains and lifted her from the rock, and the people of Aethiopia cheered from the shore. He built three altars on the spot, one to Zeus, one to Hermes, and one to Athena, and made sacrifices to thank the gods for the victory.

The wedding feast was prepared in the palace of Cepheus, rich with garlands and incense, but it was interrupted by Phineus, the brother of King Cepheus and Andromeda's uncle, who claimed that Andromeda had been promised to him long before Perseus arrived. Phineus and his men burst into the banquet hall with weapons drawn, and a battle broke out. Cepheus tried to reason with his brother, reminding him that he had done nothing to save Andromeda from the monster while Perseus had risked his life, but Phineus would not listen. Perseus, outnumbered, reached for the wallet at his side and drew forth the head of Medusa. Phineus saw the face he had dreaded, and in an instant he and his followers were turned to stone, frozen in the attitudes of attack, their spears still raised. Some versions say that Cassiopeia had encouraged Phineus and was turned to stone as well, though in most accounts she survived to be placed among the stars as the constellation Cassiopeia, condemned to circle the pole forever, half the year hanging upside down as punishment for her pride.

Andromeda followed Perseus to his home island of Seriphos, where he rescued his mother Danae from the unwanted advances of the island's king, Polydectes, by turning him to stone with Medusa's head. From there they travelled to Argos, where Perseus was the rightful heir to the throne of his grandfather Acrisius, the king who had once locked Danae in a bronze tower to prevent the prophecy that her son would kill him. The prophecy came true anyway: Perseus, competing in funeral games, threw a discus that struck and killed Acrisius by accident. Unwilling to rule the city where he had shed kindred blood, Perseus swapped kingdoms with his cousin Megapenthes and became king of Tiryns instead. Later he founded Mycenae, and Andromeda reigned beside him as queen.

Andromeda bore Perseus seven sons and two daughters. Their children were Perses, from whom the Persian kings claimed descent; Alcaeus; Heleus; Mestor; Sthenelus; Electryon; Cynurus; Autochthe; and Gorgophone. Through Electryon, Andromeda became the grandmother of Alcmene, the mother of Heracles, the greatest hero of Greece, which means that Andromeda's blood ran in the veins of the man who would one day complete twelve impossible labours. When Andromeda died, Athena, the goddess who had guided Perseus through every trial, placed her among the stars as the constellation Andromeda, her limbs outstretched in the same pose she had held upon the rock, forever between the constellation Perseus and the constellation Cassiopeia, the family reunited in the sky. The Andromeda Galaxy, the largest galaxy nearest to our own Milky Way, lies within her constellation, a reminder that the princess who was chained to a rock by the sea would one day give her name to something far larger than any kingdom on earth.