The story begins before the birth of either Andromeda or Perseus. In the land of Argolis there was a great warrior-king named Abas. He was a man so mighty that even after he died the sight of his shield would send rebels to the royal house scattering in fear. He had two twin sons to whom he gave the responsibility of ruling the kingdom. He charged that they should each rule a year, and then switch. But the twins, Acrisius and Proetus, weren't content with this arrangement, and when Acrisius refused to give up the throne at the end of his term, Proetus launched a bloody assualt on the kingdom. Eventually the brothers agreed to split the kingdom up; Acrisius got Argos and Proetus got the rest.
Acrisius, married to Aganippe (which, just for curiosity's sake, means "mare who kills mercifully"), had no sons but did father the child Danae. He wanted a male heir, and asked an oracle how that might occur. The oracle answered, "You will have no sons, and your grandson must kill you." Acrisius immediately locked his daughter in a dungeon with bronze doors guarded by savage guards, but what are bronze and dogs against Ananke (Fate) and Zeus. Zeus appeared to Danae in a shower of gold (see below) and impregnated her.
When Acrisius learned of his daughter's pregnancy, he wasn't about to believe her story of Zeus and golden showers, and suspected his brother Proetus (who had romanced Danae earlier). Not daring to kill poor Danae, he locked his daughter and the young Perseus (her son) into a casket and ordered it pushed into the sea, saying "If she dies, it be on Poseidon's head."
The casket didn't drown, miraculously, and was hauled ashore on the island of Seriphos by a kind old fisherman named Dictys. He took the two at once to his brother, King Polydectes, who raised Perseus. As Perseus grew he found his situation difficult. He had to protect his beautiful mother against the advances of Polydectes. Polydectes couldn't just kill Perseus, but he did want to get rid of him, so he told all his friends and announced that he was planning to beg the hand of Hippodameia. With this announcement he asked for one horse from each of them as a love-gift. Perseus, of course, had no such thing, but offered to bring him anything else - exulted that he would no longer be chasing Danae. Polydectes asked him to bring him the head of Medusa. (sound effect: *duh duh DUHHHHHH*)
Now, the Gorgon Medusa had serpents for hair, huge teeth, a protruding tongue, and a face so hideous that anyone who looked upon it was turned to stone. Athena happened to hear this little exchange, and recognized the potential of the hero, and decided to help him out. Besides that, she was a sworn enemy of Medusa's and actually the one responsible for her horrible looks. She took the young hero to Samos and showed him pictures of the three Gorgons so he would recognize which was Medusa and which were her sisters. Then she gave him a beautifully polished shield and told him to look at Medusa's reflection in it, but never to look at her directly. Hermes gave Perseus an adamantine sickle to cut off the Gorgon's head. But Perseus still needed a pair of winged sandals, a magic wallet for the head (post-decapitation), and Hade's helmet of invisibility. Athena knew exactly where to go, to the Stygian Nymphs, but their location was known only to the Graeae who shared a single eye and tooth among the three. Perseus sneaked up on and stole their eye while they were passing it and refused to give it back until they told him where the Stygian Nymphs lived. Upon learning, he threw the eye into Lake Tritonis (not very nice).
With his new handy-dandy flying shoes he flew to the end of the world to the land of the Hyperboreans (to the northwest) where the sun and moon never shown. He found and entered the lair of the Gorgons and lay in wait among the rain-worn statues of men and beasts. The Gorgons were asleep and Perseus, viewing Medusa using his shield like a mirror and guided by Athena, cut off Medusa's head with one stroke of his sickle. It must have shocked everyone concerned when Pegasus the winged horse and the warrior Chrysaor sprang fully grown from her corpse. (They were the products of Medusa's union with Poseidon in Athena's temple, which was why Athena transformed Medusa in the first place.) Perseus decided to leave them alone and quickly took his leave. Good thing too, because Pegasus' neigh woke the other Gorgons (Euryale and Stheno) who immediately started chasing Perseus. Perseus slipped on Hades' helmet and was safe.
Now we pause our story to visit the fair land of Joppa. Here is the kingdom of the Ethiopian King Cepheus and Queen Cassiopeia. Cassipeia wasn't exactly the smartest woman, and boasted that she and Andromeda, her daughter, were more beautiful than the Nereids. This didn't make the Nereids too happy and they complained about the insult to their protector, Poseidon. Poseidon wasn't very pleased about the lack of respect shown his wards, and sent a flood and a female sea-monster to wreck havoc on the country. Cepheus consulted the Oracle of Ammon, who told him to sacrifice a young woman. For a while he sacrificed the daughters of others, but eventually the time came when Andromeda, his own daughter was chosen. He didn't want to consign his daughter to death, but he didn't have much choice, because the monster was returning. Therefore, he left her chained to a rock jutting from the sea; she was naked but for some jewels (but hey! half the joy of a dish is the presentation, right?). Now, Andromeda was already engaged to a dude named Agenor, but Agenor was a wus, and never even tried to stand up for his fiance.
So, Perseus is flying across the world. He made a couple of stops, made some sacrifices, got some cults, but as he rounded the coast of Philistia he saw this beautiful naked woman chained to a cliff. Hmmmmm. Real hard to imagine what must have gone through his head. The young hero noticed an anxious looking couple near the rock, and swooped down for a brief chat. They explained the situation to him, and Perseus responded that he would rescue her if they would give him Andromeda's hand in marriage and allow her to return to Greece with him. They agreed and he took to the air, dove into the sea, and beheaded the monster as it came for the maiden.
Upon returning to land he made sacrifices to Hermes, Athena, and Zeus (a calf, cow, and bull, respectively), and, on Andromeda's insistence (for she loved Perseus as much as he loved her) had the wedding immediately. The post-wedding party was crashed by Agenor claiming Andromeda for himself. Now, you'd think her parents would have laughed and told him he should have saved her himself, but no! They weren't those kind of people. In fact, they had summoned Agenor, telling him that her hand had been forced and the Agenor's claim was prior. Perseus put up a good fight on his own, but in the end was forced to use Medusa's head and turn them all to stone.
Perseus and Andromeda hurried back to Seriphos and found that the treacherous King Polydectes had indeed gone after Danae, and that she and Dictys were hiding in a temple. Perseus went straight to the palace and proclaimed he had brought his wedding gift. Of course a tirade of insults were thrown at him, and Perseus, shielding his eyes, pulled out the head and turned them all to stone as well (there is still a circle of stones in Seriphos). After that he gave Medusa's head to Athena, saying that he couldn't deal with the responsibility, and returned the other gifts to Hermes who, in turn, returned them to their rightful owners. Dictys took over the throne. You'd think the story was over. But it isn't.
Perseus, Andromeda, Danae, and some Cyclopes decided it was time to return to Argos. Acrisius, hearing of their return, fled to Pelasgian Larissa. Unfortunately, while he was there, the King of Larissa invited Perseus to the funeral games being held, and Perseus' discus was carried out of its path and struck Acrisius, killing him. Perseus returned to Argos and buried his grandfather, but could not feel right about ruling there, so he and his cousin (the son of Proetus) switched kingdoms and Perseus began ruling Tiryns, Midea, and Mycenae.