Andromeda era figlia di Cassiopea e di Cefalo, il Re di Etiopia. La regina dei Cefei ebbe però l’arroganza di proclamarsi più bella delle Nereidi del mare (secondo altre versioni Cassiopea affermava che lei e la figlia fossero le donne più belle mai esistite). Queste ultime, insieme ad Hera, profondamente risentite per l’ardita asserzione di Cassiopea, avevano chiesto al Dio dei Mari di vendicarle per l’onta subita. Poseidone, per accontentare le cinquanta figlie di Nereo, scatenò la sua furia sulle coste dell’Etiopia che vennero sferzate da onde gigantesche. Quando le acque si ritirarono rimase, però, un enorme mostro affamato (chiamato Tiamat secondo alcune fonti) che terrorizzava la popolazione costringendola a barricarsi in casa. Cefalo consultò l’oracolo per sapere cosa avrebbe dovuto fare per placare l’orribile bestia ma il responso che gli fu dato era tremendo. Infatti occorreva sacrificare Andromeda, l’unica e bellissima figlia del re, che era stata promessa in sposa a Fineo, il fratello del padre. Il re di Etiopia e la sua sposa Cassiopea tergiversavano, incapaci di prendere una decisione, sicché irruppero nella reggia i sudditi inferociti che trascinarono Andromeda sulla spiaggia e la incatenarono alla rupe sovrastante. Fortuna volle che giungesse nella terra dei Cefei Perseo, l’eroe che aveva reciso la testa di Medusa. Il gorgonicida propose al re un patto: avrebbe liberato la splendida fanciulla a patto che gli fosse data in sposa. Cefalo accettò senza alcuna esitazione questa richiesta e così Perseo liberò Andromeda uccidendo la terribile bestia con la falce donatagli da Hermes. Altre versioni riportano che Perseo stava per avere la peggio e dovette fare ricorso al potere del capo della Gorgone per eliminare la fiera marina. Il sangue del mostro si mescolò alle alghe sopra le quali Perseo aveva adagiato la testa di Medusa: così le alghe color porpora si pietrificarono e nacquero i coralli. Le Nereidi, ammaliate e stupite dalla straordinaria trasformazione di semplici alghe in rametti rosati, fecero a gara per raccogliere i coralli e dimenticarono l’astio che provavano nei confronti della regina Cassiopea. Il figlio di Danae, per ringraziare gli Dei che lo avevano assistito durante le sue imprese, innalzò tre altari a tre numi del cielo: l’uno a Mercurio che gli aveva dato la falce, l’altro ad Atena che lo aveva guidato nelle sue azioni e il terzo a Zeus, il padre degli Dei. Durante il banchetto che celebrava sia la liberazione del regno che le nozze tra l’eroe e la bellissima figlia del Re si levò il pusillanime Fineo, che nulla aveva fatto per salvare la giovane fanciulla, per reclamare i suoi diritti su Andromeda. La maggior parte del popolo sostenne le pretese di Fineo, irruppe nella reggia e così il banchetto si trasformò in un bagno di sangue. Perseo riuscì ad avere la meglio sui nemici tramutandoli in pietra grazie ai poteri della testa di Medusa e non ebbe pietà di Fineo che, tremante, lo supplicava di risparmiarlo; infatti regalò ad Andromeda una bellissima statua di marmo, raffigurante lo sposo assegnatole dal padre, vecchio, curvo, spaventato, con le braccia tese in un vile gesto di supplica. Dopo questi fatti Perseo decise di partire, con la sposa stretta tra le sue possenti braccia, verso Serifo in soccorso della madre. Lì, mentre era ancora in corso un banchetto, Perseo impietrì anche Polidette, liberò la madre dalla schiavitù e con Danae e Andromeda se ne tornò ad Argo. Gli Dei posero in cielo le costellazioni raffiguranti ognuno dei protagonisti di questa storia: Andromeda, Cefalo (Cefeo), Cassiopea, Perseo e Balena (il mostro marino). Ma, volendo punire ugualmente la tracotanza di Cassiopea, condannarono la sposa di Cefalo a girare per sempre col suo trono intorno al Polo Nord prima di tramutarsi in costellazione.
Le radici di questo mito risalgono al V secolo avanti cristo. Secondo alcuni storici la rupe nella quale venne incatenata Andromeda è da collocarsi vicino a Giaffa e un monaco del XV secolo, Felice Fabri, raccontò che le ossa della fanciulla vennero spedite a Roma dall’imperatore Tito ed esposte in una piazza; ma San Silvestro e gli altri, che consacrarono Roma al cristianesimo, le frantumarono e le dispersero. Alcuni studiosi reputano che nella mitologia persiana sia presente una storia del tutto analoga: l’eroe divino Thraetona doveva salvare non una donna ma un intero harem da un drago (anziché un mostro marino) custode di una sorgente che sgorgava dalle rocce dove le bellissime vergini sono incatenate. Thraetona, sconfisse il mostro e liberò le fanciulle e le acque. Cadde allora la pioggia fecondatrice della terra, mentre il giovane eroe liberatore celebrava i giochi sacri con le donne che aveva salvato; pertanto il mito è connesso con la fine della siccità. Infine anche nella leggenda di San Giorgio, che combatte un drago a forma di serpente, uscito dal mare, per liberare la figlia di un re, si può riscontrare una certa rassomiglianza con il mito greco di Andromeda.