Illustrating Franco-Maghrebi crossings from cultural and political standpoints par excellence, Baya Mahieddine (born Fatma Haddad) becomes the perfect intermediary between Algeria and France. Born in Fort-de-l’eau (today’s Bordjel-Kiffan) in 1931, she loses both parents by the age of eleven. According to some accounts about Marguerite Caminat, a French woman and artist residing in Algiers, she appears in the orphan’s life as an idealized “bonne fée” who rescues her from poverty and neglect (Charles-Roux 7). In addition to these allusions to Cendrillon from popular culture, other sources compare Baya to Scheherazade in order to highlight the artist’s giftedness as a visual storyteller. Yet, in what ways does Baya’s positive reception among artists, curators, and writers on both sides of the Mediterranean indicate how she involuntarily functioned as a transnational icon conceived at the Franco-Algerian crossroads, and how does she transcend this imposed iconography through her own agency? In order to answer these questions, this article first considers how and why some of her writers romanticize her as a legendary figure both before and after Algeria’s independence, while others present her in a more earthly context. Then, from a postcolonial angle, this article seeks to resituate the artist more concretely in her sociocultural background in order to demonstrate that she modeled an Algerian woman’s trajectory of survival.