Andromeda is the princess of Ethiopia and there are references to her being a dark-skinned woman, most famously by the poet Ovid.