Mylène Farmer doesn't grant many interviews, but for Sting, she'll make an exception. The French pop star, who has sold 11 million albums worldwide and regularly sells out stadiums throughout the French-speaking world, recently debuted a version of Sting's 2004 song "Stolen Car," in which she and the ex-Police man duet in French and English. Last month, the track debuted in France at Number One on iTunes, and stayed there for four days. It's now available in the U.S., to be followed with a video next month.

Sting, it turns out, is perfectly equipped to steal a fancy car and run off with a Frenchwoman, as he does in the video - he's fluent in French. The two sat down with Rolling Stone ahead of the November 6th release of Interstellaires - Farmer's 11th studio album, which will feature "Stolen Car" and is available for preorder October 3rd - to talk about pilfering cars in two languages.

How did you two meet and end up collaborating?

Farmer: A few years ago, I went to London to see one of his shows that was happening in a church [Songs from the Labyrinth at St. Luke's Church]. I thought that was very impressive, very beautiful and poetic. Then [last year], I flew to New York because I really wanted to see his play, The Last Ship, and I found it very moving and dark. The songs were very beautiful, the acting amazing - I fell in love with it. And then I asked him if he would like to do something with me. And he said, "Yes, why not."

Sting: I was very happy that Mylène came to my show, obviously, and we met, and she said, "Do you have any songs that would be appropriate that we could sing together?" And immediately I thought of "Stolen Car." I'd written it almost 12 years ago. It was always designed to have a female singing in the chorus: "Take me dancing tonight." Because the girl doesn't get enough attention. She's the mistress of a successful businessman and there's a poignancy about the story. I was waiting for the right woman to sing the song, and Mylène was the perfect candidate.

What was different about singing it this time?

Sting: Well, you always pick up something from another singer when you're harmonizing together, and you're phrasing together, so you have to listen very carefully. It's very much a relationship; it's like a dance ... [And] we had to change the key, to match, so I'm singing higher than I would do normally.

Farmer: Plus it's in French and English. I asked Sting if he would agree on French lyrics and he said okay. My translation is very close to what he first wrote, and then I added a few little things that were really French and my style. Then it's really like a conversation between the two of them; that was interesting for me too.

Sting: It's very sexy in French too.

What is it like to collaborate creatively, versus working alone?

Sting: Well, it's a question of one plus one needing to make three, not two. And I think in this case, we produced something far better than I did on my own, or could do on my own. There's a dimension to it now which is wonderful.

Farmer: When I'm songwriting, I need to be on my own. Hidden in the corner of a room and then I write. I'm very desperate - it's better.

Tell me about the video.

Sting: We thought about making a video immediately. So the way [the song] was recorded had in mind how it would be filmed. It was always meant to be a visual piece as well.

Farmer: It's a French director, Bruno Aveillan, who's a very talented man and a friend of mine. He's done a lot of commercials for Cartier, Guerlain, etc. He does things very beautifully, almost like paintings. I showed Sting his work because I thought it would fit the story, because this song is already like a small movie. And he agreed. We took - was it two days?

Sting: Two 12-hour days, and we finished at four in the morning.

Farmer: He worked a lot more than I did, because he was playing two parts.

Sting: In the video, I play the car thief, and I also play the company director, so I get all the fun.

Mylène, I saw from the paparazzi photos that you were walking with a crutch during filming.

Farmer: Yes, I broke my leg five months ago in two parts, and it's almost okay now. But I had to wear high heels [in the video] and had to be very careful. [Sting] was very nice to me and very careful because I couldn't walk. He had to hold me very tight.

Sting: No problem! [Both laugh] The Daily Mail liked it too ...

Do you find any differences in the way French vs. American vs. other audiences respond to your work?

Sting: One of the great pleasures of playing in Europe is how different culturally each country is - Germany, Spain, Italy, France. The French listen very carefully to what you're singing about. I think they have a very high understanding of music; I think music is taught well in schools, so they understand harmony. I think it's part of the French soul. So I enjoy playing there. They're not quite as enthusiastic as the Italians, who just go crazy.

Farmer: Russians are quite amazing, because they're very fond of French language. They have the depth for his music I think. I would have a hard time answering [about my own experience], because I'm very used to a French audience. Americans, I don't know. I still have to see.

Can each of you remember the first time you heard each other's music?

Farmer: I knew of him for a long time as an artist, and I'm very fond of his music. If I had to pick one which is very difficult I would take probably Fragile - I would love to just steal the song and pretend it's mine. And … [Sting] you don't have to answer because I don't think he knows all of my work...

Sting: Yeah I'm a friend of her manager, and he produced a play I did in Paris a few years ago called Welcome to the Voice, and I became aware of Mylène then. It's important to recognize how big a star she is in the French-speaking world - she fills all these giant stadiums again and again and again, so she's massive, and rightly so, and a lovely person. Which is more important, actually.

Farmer: Merci. I agree; thank you.

(c) Rolling Stone by Eveline Chao