Eufemia era la hija de un senador llamado Filofronos y de su mujer Teodosia, de Calcedonia (Bitinia), localidad en la entrada oriental del Bósforo, enfrente de la ciudad de Bizancio, posteriormente denominada Constantinopla y actualmente Estambul.