D’adolescent actuà en una telesèrie. Estudià periodisme i producció en mitjans audiovisuals a la Universitat Linneu de Kalmar i produí documentals de tema musical per a la televisió pública SVT. Posteriorment viatjà fent la volta al món i durant aquest periple conegué la història del cantant nord-americà Sixto Rodríguez, a partir de la qual filmà amb mitjans molt precaris el seu únic film, el documental Searching for Sugar Man, que narra la cerca i el retrobament des de Sud-àfrica d’aquest cantant dels anys setanta desaparegut de l’escena artística. Estrenat el 2013, fou un èxit internacional i obtingué un gran nombre de premis, entre d'altres, el BAFTA i l’Oscar al millor documental. Bendjelloul se suïcidà.