Dalam perjalanan pulang ke Serifos, Perseus mengalami banyak petualangan, di anataranya dia melihat Atlas yang sedang memikul langit. Perseus merasa kasihan dan menunjukan padanya kepala Medusa sehingga Atlas berubah menjadi batu dan tak lagi merasa letih.
Perseus mengubah Atlas menjadi batu.
Perseus terbang dengan cepat ke arah selatan. Esok harinya, ia terbang melintasi Gurun di Libya, beberapa tetes darah medusa jatuh ke pasir dan munculah sekumpulan ular berbisa di gurun itu. Perseus melanjutkan perjalanannya dan melihat sebuah patung yang dirantai pada batu karang. Setelah diamati, ternyata itu bukanlah patung melainkan seorang perempuan. Perseus mendekati perempuan itu dan bertanya kenapa dia dirantai di tengah laut.
Gadis itu pun bercerita. Dia adalah Andromeda, Putri dari Kefeus dan Kassiopia. Kassiopia pernah menyombongkan bahwa putrinya lebih cantik dari para Nereid, putri-putri Poseidon. Para Nereid mendengarnya dan melaporkan hal tersebut pada ayah mereka. Sang ayah pun marah dan mengirimkan bencana serta seekor monster laut yang bernama Ketos ke kerajaan yang dipimpin oleh Kefeus.
Perseus bertarung melawan Ketos.
Ketika Kefeus berkonsultasi pada Orakel, ia diberitahu bahwa satu-satunya harapan adalah dengan mengorbankan putrinya sendiri kepada Ketos. Akhirnya Kefeus pun melakukannya, Ia merantai putrinya di sebuah batu karang dan membiarkannya agar dimakan oleh Ketos.
Selesai ia bercerita, tiba-tiba dari laut munculah seekor monster yang sangat besar. Perseus bertarung dengan monster itu. Dia menggunakan kepala Medusa dan monster itu pun berubah menjadi batu. Perseus lalu menghancurkannya dengan pedangnya. Perseus membebaskan Andromeda dan membawanya pada ayahnya, raja Kefeus, untuk meminta izin menikahi Andromeda.
Kefeus menggelar pesta untuk Perseus dan Andromeda. Namun pesta itu diganggu oleh Finius yang dulu dijanjikan oleh Kefeus untuk dinikahkan dengan Adromeda. Perselisihan pun terjadi antara pendukung Finius dengan pendukung Perseus.
Untuk menghentikan semua ini, Perseus pun mengeluarkan kepala Medusa. Namun dia terlebih dahulu menyuruh teman-temannya untuk menutup mata mereka sehingga Finius dan para pendukungnyalah yang menjadi batu.
Perseus dan Andromeda kemudian menikah dan memiliki anak bernama Perses. Perseus lalu pergi bersama Andromeda menuju Serifos sementara Perses ditinggal untuk mewarisi tahta dari Kefeus.
Perseus mengubah Finius dan anak buahnya menjadi batu.
