メデューサの首を取ったペルセウスは故郷の島に帰ります。ヘルメスにもらったサンダルで空を飛んでギリシャへ向かいました。
帰る途中、エチオピアの上空を飛んでいると、裸の若い娘が海上の岩に縛り付けられているのを発見しました。しかも海から出てくる怪物に襲われそうになっています。
彼女はエチオピアの王の娘で、名前はアンドロメダと言いました。
アンドロメダの母カシオペアが、自分の容姿を自慢して、「私は海の女神ネレイデスの誰よりも美しい」と豪語したところ、海神ポセイドンが怒って津波を起こしたのです。ネレイデスはポセイドンの娘で、全部で50人とも100人とも言われます。津波を鎮めるためには、カシオペアの娘アンドロメダをいけにえに捧げなければいけません。
ペルセウスは、エチオピアの王を訪ね、海の怪物を倒してアンドロメダを救出したら嫁に欲しいと頼みました。
そしてメデューサの首を使って海の怪物を石にして退治し、アンドロメダの鎖をほどきました。
ペルセウスがアンドロメダを連れてエチオピアの王のところへ行くと、アンドロメダと婚約していた王の弟が襲ってきました。
これも、味方の人間には伏せるように言ってメデューサの首を見せて石にしました。
ペルセウスはアンドロメダを嫁にもらい、故郷のギリシャへ向かいました。
なお、唐突にエチオピアが出てきましたが、ギリシャ神話が作られた頃のギリシャ人の行動範囲がエチオピアまで及んでいたかは不明です。ただ、実際に行ったかどうかは別として、存在は知っていたことになります。また、イスラエルの近くにあった似た名前の別の国だという説もあります。