Here's one version of Perseus and Andromeda's story, as told by Thomas Bulfinch in The Age of Fable. For more variations on the story, visit Theoi.com.
Perseus, continuing his flight, arrived at the country of the AEthiopians, of which Cepheus was king. Cassiopeia, his queen, proud of her beauty, had dared to compare herself to the Sea- Nymphs, which roused their indignation to such a degree that they sent a prodigious sea-monster to ravage the coast. To appease the deities, Cepheus was directed by the oracle to expose his daughter Andromeda to be devoured by the monster. As Perseus looked down from his aerial height he beheld the virgin chained to a rock, and waiting the approach of the serpent. She was so pale and motionless that if it had not been for her flowing tears and her hair that moved in the breeze, he would have taken her for a marble statue. He was so startled at the sight that he almost forgot to wave his wings. As he hovered over her he said, "O virgin, undeserving of those chains, but rather of such as bind fond lovers together, tell me, I beseech you, your name and the name of your country, and why you are thus bound." At first she was silent from modesty, and, if she could, would have hid her face with her hands; but when he repeated his questions, for fear she might be thought guilty of some fault which she dared not tell, she disclosed her name and that of her country, and her mother's pride of beauty. Before she had done speaking, a sound was heard off upon the water, and the sea-monster appeared, with his head raised above the surface, cleaving the waves with his broad breast. The virgin shrieked, the father and mother who had now arrived at the scene, wretched both, but the mother more justly so, stood by, not able to afford protection, but only to pour forth lamentations and to embrace the victim. Then spoke Perseus: "There will be time enough for tears; this hour is all we have for rescue. My rank as the son of Jove and my renown as the slayer of the Gorgon might make me acceptable as a suitor; but I will try to win her by services rendered, if the gods will only be propitious. If she be rescued by my valor, I demand that she be my reward." The parents consent (how could they hesitate?) And promise a royal dowry with her.
And now the monster was within the range of a stone thrown by a skilful slinger, when with a sudden bound the youth soared into the air. As an eagle, when from his lofty flight he sees a serpent basking in the sun, pounces upon him and seizes him by the neck to prevent him from turning his head round and using his fangs, so the youth darted down upon the back of the monster and plunged his sword into its shoulder. Irritated by the wound the monster raised himself into the air, then plunged into the depth; then, like a wild boar surrounded by a pack of barking dogs, turned swiftly from side to side, while the youth eluded its attacks by means of his wings. Wherever he can find a passage for his sword between the scales he makes a wound, piercing now the side, now the flank, as it slopes towards the tail. The brute spouts from his nostrils water mixed with blood. The wings of the hero are wet with it, and he dares no longer trust to them. Alighting on a rock which rose above the waves, and holding on by a projecting fragment, as the monster floated near he gave him a death-stroke. The people who had gathered on the shore shouted so that the hills re-echoed to the sound. The parents, transported with joy, embraced their future son-in-law, calling him their deliverer and the savior of their house, and the virgin, both cause and reward of the contest, descended from the rock.
The joyful parents, with Perseus and Andromeda, repaired to the palace, where a banquet was spread for them, and all was joy and festivity. But suddenly a noise was heard of war-like clamor, and Phineus, the betrothed of the virgin, with a party of his adherents, burst in, demanding the maiden as his own. It was in vain that Cepheus remonstrated, "You should have claimed her when she lay bound to the rock, the monster's victim. The sentence of the gods dooming her to such a fate dissolved all engagements, as death itself would have done." Phineus made no reply, but hurled his javelin at Perseus, but it missed its mark and fell harmless. Perseus would have thrown his in turn, but the cowardly assailant ran and took shelter behind the altar. But his act was a signal for an onset by his band upon the guests of Cepheus. They defended themselves and a general conflict ensued, the old king retreating from the scene after fruitless expostulations, calling the gods to witness that he was guiltless of this outrage on the rights of hospitality.
Perseus and his friends maintained for some time the unequal contest; but the numbers of the assailants were too great for them, and destruction seemed inevitable, when a sudden thought struck Perseus: "I will make my enemy defend me." Then, with a loud voice he exclaimed, :If I have any friend here let him turn away his eyes!" and held aloft the Gorgon's head. "Seek not to frighten us with your jugglery," said Thescelus, and raised his javelin in act to throw, and became stone in the very attitude. Ampyx was about to plunge his sword into the body of a prostrate foe, but his arm stiffened and he could neither thrust forward nor withdraw it. Another, in the midst of a vociferous challenge, stopped, his mouth open, but no sound issuing. One of Perseus's friends, Aconteus, caught sight of the Gorgon and stiffened like the rest. Astyages struck him with his sword, but instead of wounding, it recoiled with a ringing noise.
Phineus beheld this dreadful result of his unjust aggression, and felt confounded. He called aloud to his friends, but got no answer; he touched them and found them stone. Falling on his knees and stretching out his hands to Perseus, but turning his head away, he begged for mercy. "Take all," said he, "give me but my life." "Base coward," said Perseus, "thus much I will grant you; no weapon shall touch you; moreover you shall be preserved in my house as a memorial of these events." So saying, he held the Gorgon's head to the side where Phineus was looking, and in the very form in which he knelt, with his hands outstretched and face averted, he became fixed immovably, a mass of stone!