La costellazione raffigura una donna incatenata: trattasi della figlia della Regina Cassiopea e del Re Cefeo. Come raccontato nella costellazione di Cassiopea, quest'ultima osò considerarsi più bella delle Nereidi, che offese chiesero a Nettuno di darle una bella lezione. Il dio del mare mandò un mostro marino (ricordato nella costellazione del Cetus) a razziare le coste del regno e i due inetti sovrani decisero di sacrificare la propria figlia Andromeda al mostro per placarlo. La bellissima fanciulla venne quindi incatenata ad uno scoglio (alcuni dicono nei pressi della moderna Tel Aviv) in attesa del suo terribile destino. Perseo, l'eroe che decapitò Medusa, appena di ritorno dalla sua grandiosa impresa, si trovava nei paraggi e rimase folgorato dalla bellezza indifesa della fanciulla. Perseo si avvicinò ad Andromeda che a differenza della madre era molto timida e non osò rivolgergli lo sguardo nemmeno in un momento così delicato, ma alla fine si decise a raccontargli la sua storia. Il mostro intanto emerse all'improvviso dalle acque ed era pronto ad azzannarla: l'eroe senza indugio chiese ed ottenne la mano di Andromeda ai genitori e si gettò a capofitto sul mostro trafiggendolo con la sua spada. I due si sposarono ed ebbero sei figli, tra cui Perses, il progenitore dei Persiani.
In cielo Andromeda si trova nei paraggi delle costellazioni che raffigurano i personaggi della sua storia: Cefeo, Cassiopea, Perseo e Ceto.
Le stelle più brillanti di Andromeda sono: alfa Andromedae, detta anche Sirrah o Alpheraz, rispettivamente dall'arabo surrat, "ombelico", e al-faras, "il cavallo", perché prima questa stella era condivisa con la costellazione di Pegaso e ne rappresentava l'ombelico. Della stessa magnitudine c'è poi beta Andromedae, detta anche Mirach, che deriva dall'arabo al-mi'zar, "guaina" o "perizoma