Note: This interview originally ran as part of our coverage of the 2012 Tribeca Film Festival. Searching for Sugar Man opens theatrically on Friday, July 27, in New York and Los Angeles, with more cities to follow in the coming weeks.

Tribeca: Tell us a little about Searching for Sugar Man. How do you describe the movie in your own words?

MALIK BENDJELLOUL: Searching for Sugar Manis a movie in two parts: the first part is a mystery, and the second part is about the incredible consequences caused by the solution to that mystery.

TRIBECA: Let’s start from the beginning. You are from Sweden, a first time filmmaker, and you decided to make a film about the “South African Elvis.” How did you come across the story of Rodriguez and the South African fans who love him? What inspired you to make this film?

MALIK BENDJELLOUL: I was traveling around Africa and South America for six months with a camera, scouting good stories. I found six pretty good ones, but the story about Rodriguez just blew my mind. It was so beautiful and intriguing. I never heard a better story in my life, and then I heard Rodriguez's music, and the story was suddenly twice as good. When the South Africans told me Rodriguez was as famous and as good as the Rolling Stones or Bob Dylan, I thought they were crazy at first. But when I heard the actual music, the comparison made every sense in the world.

TRIBECA: Given that your background is largely in short documentaries, was it always your intention to make a feature length documentary?

MALIK BENDJELLOUL: My background is making short docs. My first years working I did documentaries about musicians. I did docs centered on interviews with artists like Björk, Kraftwerk, Sting, Rod Stewart and Elton John. After three years of meeting lots of great artists, I started to understand that a doc never gets better than the story it tells, and I started to go after good stories. Not famous people, just good stories.

I did, for example, a story about The First Battalion, the secret U.S. army division that tried to teach people how to walk through walls. I thought that the Rodriguez story was the king of all good stories.

TRIBECA: In addition to telling this amazing story, Searching for Sugar Man also explores the civil unrest that enveloped white South Africa as a result of Apartheid. Why do you think that Rodriguez, a Latin musician, became the voice of the anti-Apartheid movement? Were the people you approached about the Rodriguez phenomenon mostly willing to talk about these troubled times in their country?

MALIK BENDJELLOUL: There weren't any famous artists singing songs with anti-establishment messages in South Africa in those times. You weren't allowed to, and consequently Rodriguez was banned. You couldn't hear him on South African radio. But somehow you could buy the records, and for the liberal youth in South Africa, those songs became explosive. The first real white resistance to the Apartheid system in South Africa came from South African rock bands, and to those bands, Rodriguez was the guy who opened their eyes. He told them that music could change the world. In those days, those bands really took a risk. You could be arrested for three years without a trial for protesting against the regime.

Now the society is completely different. It was not hard to get people to talk about the troubled times, because I think people are pretty proud of the way South Africa has changed into a functioning democratic state. The South Africa Rodriguez came to in 1998  had, just a few years earlier, been through this beautiful metamorphosis where the values those liberals had believed in had prevailed—the country was free.

TRIBECA: Rodriquez and his family seemed very receptive to your documentary. They are reserved and humble, but all gave such fascinating interviews. How did you approach them?

MALIK BENDJELLOUL: Yes, they are a beautiful family. They have experienced so much and have a very humble and intelligent way of dealing with life. There's no bitterness when you ask them if it wouldn't have been nice to learn 30 years earlier that Rodriguez was a superstar on the other side of the planet. Rodriguez has had a good life. Maybe the family didn't have the material wealth that probably would have been the result of learning about his stardom, but they still felt rich in many other ways.

Many of the artists who made it big in the days when Rodriguez made his albums aren't with us anymore: Jimi Hendrix, Jim Morrison, Janis Joplin. Rodriguez had his career in a very unusual order. Rodriguez turns 70 this summer, and there's a fair chance that his best days are still to come.

TRIBECA: I loved your use of archival footage in Searching for Sugar Man. It gave the film an authenticity that mirrors Rodriguez himself. Your film, like its subject, has no pretense. While most of the footage came from Rodriguez’s daughters, how did you obtain the rest?

MALIK BENDJELLOUL: I was searching through archives. I found a good one at the university in Detroit, and Swedish TV had quite a lot about the Apartheid. I love the romantic feeling that is found in Super 8 footage. In Cape Town, I asked Stephen "Sugar" Segerman to put up an ad in his record shop, asking if anyone had some home made Super 8 movies from South Africa in the 70s. This girl came in with quite a lot of beautiful stuff that was exactly what I was looking for. These kind of scenes, with normal everyday life, is often hard to find in professional film archives that mostly focus on news and other important events.

TRIBECA: Of course, the music in Searching For Sugar Man is fantastic. Rodriguez is such an incredible artist, but difficult to define. How would you describe his music? Do you have some favorite Rodriguez songs?

MALIK BENDJELLOUL: People tend to label his music folk, but I think those two albums he made are not any more folk than the Beatles are folk. His songs are very different. They were just very good songs. My favorites are probably "Crucify Your Mind", "Cause" and "Like Janis."

TRIBECA: What do you want audiences to take away from Searching for Sugar Man?

MALIK BENDJELLOUL: I hope they will feel something; emotional reactions are the most powerful when you go to the cinema, I think. This is a pretty uplifting story. Those who cry when they see the film tend to cry happy tears. If people are moved by the film, that's just everything I could ever dream of. The first question at almost every Q&A has been, “Where can I get hold of the music?” That would be another wonderful thing, if his music will be more known.

TRIBECA: What's your advice for aspiring filmmakers? Is there one particular thing you learned?

MALIK BENDJELLOUL: Take your time, especially if it's your first film. There are a lot of things that you need to figure out that you eventually will figure out if you have enough time. Things are slow anyway. It takes time to get funding, it takes time to convince people of your vision, but that might also be something that you will benefit from in the end, because even if it wasn't deliberate, it somehow forced you to work harder on your idea.

TRIBECA: If you could have dinner with any filmmaker (alive or dead), who would it be?

MALIK BENDJELLOUL: David Lynch or Stanley Kubrick.

TRIBECA: What’s your favorite New York movie?

Malik Bendjelloul: I really like Martin Scorsese's After Hours. It's not supposed to be one of his greatest films, but it somehow is the one that I see again and again.

TRIBECA: What would your biopic be called?

MALIK BENDJELLOUL: In the last scene of After Hours, a jukebox plays the Peggy Lee song entitled Is that all there is? That's a good title for a biopic.

TRIBECA: What makes Searching for Sugar Man a Tribeca must-see?

MALIK BENDJELLOUL: I still believe that the story behind Searching for Sugar Man is the best true story I have ever heard. The responsibility of a film director is to try to make a film that is as good as the story. I don't know if I succeeded, but I did my very best for almost four years. And you will hear some fantastic songs, probably for the first time in your life.

Malik Bendjelloul has been directing music docs for 12 years with subjects like Kraftwerk, Bjork, Madonna, and U2. He recently directed a filmed concert with Prince. He made short documentaries for Swedish television that became the basis for the films The Men Who State at Goats and The Terminal.

Searching for Sugar Man opens theatrically on Friday, July 27, in New York and Los Angeles, with more cities to follow in the coming weeks.

 Like the film? Check out the soundtrack! Searching for Sugar Man: The Original Motion Picture Soundtrack is now available through Legacy Recordings. 

 Like Searching for Sugar Man on Facebook.