팔레스타인에 있었던 요파(에티오피아)의 케페우스 왕과 카시오페이아 여왕의 딸이며 페르세우스의 아내이다. 카시오페이아가 자기 딸 안드로메다를 네레이스들보다 더 아름답다고 자랑했기 때문에, 화가 난 포세이돈이 바다괴물을 보내 케페우스의 왕국을 파괴하려 했다. 안드로메다를 제물로 바쳐야만 재난을 면할 수 있었기 때문에 그녀는 바위에 묶인 채 괴물에게 잡아먹히게 될 운명이었다. 마침 날개 달린 말 페가소스를 타고 지나가던 페르세우스가 안드로메다에게 반해 케페우스에게 그녀를 구출하겠다고 요청했다. 케페우스는 이 요청을 받아들였고 페르세우스는 괴물을 죽였다. 그러나 그들의 결혼식에서 원래 안드로메다와 결혼하기로 되어 있었던 삼촌 피네우스가 그녀를 요구하자, 페르세우스는 메두사의 머리를 보여 그를 돌로 만들어버렸다. 안드로메다는 페르세우스와 결혼해 6명의 아들과 1명의 딸을 낳았다.