Her version of "Mon amie la rose" became a surprise success in France, reaching 16 on the French Singles Charts in 1999.

[5][6] Atlas returned to Belgium at age 24 and began her career with two jobs: belly dancing and being the lead singer of a Belgian salsa band.

Through recording with ¡Loca!, she met Nation-labelmates Transglobal Underground, a British ethnic electronica band with a Middle Eastern/South Asian focus.

At the time, Transglobal Underground had a top 40 hit, "Templehead", and Atlas became their lead singer and belly dancer.

Additionally in 1991, Atlas collaborated with Bauhaus/Love and Rockets/Tones on Tail guitarist and vocalist Daniel Ash on his debut solo album Coming Down.

Two years earlier, Atlas collaborated with Arnold on the album Shaken and Stirred, recording the song "From Russia with Love" for the eponymous film (originally performed by Matt Monro).

[citation needed] Her song "Gafsa" from her 1997 album Halim was used in the main soundtrack of the 2004 Korean film Bin-Jip (also known as 3-Iron) by Kim Ki-Duk.

She participated in the piece "Light of Life (Ibelin Reprise)" for the soundtrack of Ridley Scott's Kingdom of Heaven.

She contributed additional vocals on songs "Ma jeunesse fout le camp," "La Vie en rose", "Bonnie et Clyde" and "Des ronds dans l'eau."

The 2007 film Brick Lane features four songs with vocals by Atlas, "Adam's Lullaby", "Running Through the Night", "Love Blossoms" and "Rite of Passage".

[14][15] In 2008, two of Atlas' songs, "Kidda" and "Ghanwa Bossanova", were used in Shamim Sarif's romantic comedy about two women, I Can't Think Straight.

In 2008, she sang lead in the song "Habibe" from Peter Gabriel's long-awaited album and project, Big Blue Ball.

Co-produced by Samy Bishai, it explored classical instrumentation, jazz and traditional Arabic styles and was inspired by the poems of Indian poet Rabindranath Tagore.

[16][17] Atlas moved into the jazz genre with the albums Myriad Road (2015), which was produced by French Lebanese musician Ibrahim Maalouf,[18] and Strange Days (2019).

[21] As of 2009[update], Atlas was in a relationship with British Egyptian violinist Samy Bishai, who produced her 2010 release Mounqaliba.

"[27] Of her experience of working with Levy, Atlas said: "We spent a lot of time in this little room, just talking and drinking wine", recalls Natacha, "and it was like I’d known her all my life.