Timbuktu a été présenté en Compétition au Festival de Cannes 2014. Ce fut le seul long-métrage africain en compétition, qui reçut la distinction du Prix du jury œcuménique et du Prix François-Chalais. Le long métrage a également été présenté au Festival du film de Sydney 2014, ainsi qu'à celui de Toronto.
Timbuktu a été sélectionné dans la catégorie "Meilleur film en langue étrangère" pour les Oscars 2015. C'est la première fois que la Mauritanie est représentée lors de cette célèbre cérémonie.
Si Timbuktu est une fiction, l’inspiration du réalisateur, Abderrahmane Sissako, vient de faits réels. En juillet 2012, dans la petite ville d’Aguelhok au Mali, un couple d’une trentaine d’années est placé dans deux trous creusés dans le sol en place publique, puis lapidé. Dans ce village contrôlé par des hommes, leur unique faute a été d’avoir eu des enfants hors mariage. Ce n'est pas tout, puisque l'histoire de l'homme qui est racontée dans le film, est inspirée de l'exécution d'un Touareg sur la Place de Tombouctou.
Choqué par la lapidation publique de ce couple et l’absence totale de médiatisation la concernant, Abderrahmane Sissako a décidé de faire Timbuktu. "(…) maintenant je le sais, je dois raconter dans l’espoir qu’aucun enfant ne puisse apprendre plus tard que leurs parents peuvent mourir parce qu’ils s’aiment", explique-t-il.
Le film, qui est sensé se situer à Tombouctou, a été tourné près de la frontière malienne, à l’extrême Est de la Mauritanie, dans un village hautement sécurisé. Avant le début du tournage, le réalisateur Abderrahmane Sissako avait effectué des repérages dans la ville de Tombouctou, mais malheureusement entre-temps un attentat-suicide s'est produit sur la place principale. Le lieu étant devenu trop dangereux, le cinéaste a préféré déplacer le tournage en Mauritanie.
Le tournage s'est déroulé en partie dans la ville mauritanienne de Oualata, qui est très ressemblante à celle de Tombouctou. Pour que le tournage se déroule dans de bonnes conditions, l'équipe technique et les acteurs étaient protégés par l'armée mauritanienne, ainsi que par l'Etat de Mauritanie qui s'est beaucoup impliqué dans cette sécurité.
Pour la scène de la lapidation du couple, Abderrahmane Sissako avait tout d'abord pensé à la réaliser à l'aide d'images animées, pour pouvoir créer une distance et éviter qu'elle soit trop violente, comme avait pu le faire Quentin Tarantino dans le premier volume des Kill Bill en 2003. Finalement, pour Timbuktu, le cinéaste a choisi de filmer de véritables acteurs lors de cette séquence.
Pour rassurer les producteurs, Abderrahmane Sissako a annoncé que son projet de film était un documentaire, car cela coûte beaucoup moins cher à la production, alors qu'en réalité il s'agissait d'une fiction. Le réalisateur s'est tourné vers ce type de long-métrage car il souhaitait avoir davantage de liberté de création.
Trois comédiens ont été choisis au dernier moment pour le tournage. Le metteur en scène s'est aperçu que l'acteur qui devait interpréter le juge ne correspondait pas au rôle, c'est pourquoi il demanda au régisseur du film d'enfiler son costume et de passer devant la caméra, ce que le technicien fit sans hésiter. Puis, ce fut le tour de l'interprète du pêcheur qui ne plaisait pas au cinéaste. C'est finalement un piroguier qui passait par là qui a été intégré au casting. Enfin, même façon de faire pour le casting de la petite fille prénommée Toya. Celle-ci devait avoir 3 ans d'après le scénario, mais lors de la venue du réalisateur sur le lieu du casting, une jeune fille de 12 ans ne le quittait plus d'une semelle. C'est de cette manière que le rôle lui a été attribué.
Deux comédiens ont été sélectionnés à l'étranger pour Timbuktu. Pour le rôle du Touareg c'est Ibrahim Ahmed dit Pino, un musicien habitant Madrid qui a été choisi sans passer d'essai, puis, le personnage de la femme du Touareg a été attribué à Toulou Kiki, une chanteuse repérée à Montreuil.
Le personnage de Zabou dans Timbuktu existe dans la réalité. Cette ancienne danseuse du crazy-horse qui exerçait ce métier durant les années 60 est la seule femme qui, au milieu des djihadistes, possède des droits que les autres femmes n'ont pas. Le réalisateur précise : "Elle s’habille comme dans le film, elle a toujours un coq sur l’épaule et elle parle très bien français. Quand les djihadistes étaient à Gao, c’était la seule qui pouvait marcher sans se couvrir la tête, la seule qui pouvait chanter, danser, fumer, et leur dire qu’ils étaient « des connards ». Autrement dit : l’interdit est permis quand la personne est folle."