Ambas constelaciones comparten una estrella; la estrella principal de Andrómeda es, a su vez, parte del rectángulo de Pegaso.

Andrómeda era la princesa de Etiopía, hija de Cefeo y Casiopea. Como castigo a la soberbia de su madre, la princesa tenía que ser ofrecida en sacrificio a un monstruoso leviatán que amenazaba con destruir a su país. La princesa fue rescatada por Perseo, que venció al leviatán mostrándole la cabeza de la Medusa, un ser tan horrible que todo aquel que lo veía era convertido en piedra.

Pegaso, según la misma leyenda, es el caballo alado que surgió de la sangre de la Medusa.