Boris Lojkine souhaitait depuis plusieurs années faire un film sur ces livreurs à vélo qui sillonnent la ville avec leurs sacs bleu turquoise ou jaune vif, et dont la plupart sont sans papiers. Le réalisateur se rappelle : "L'image de ces livreurs à vélo me travaillait, et je me suis demandé : et si je filmais Paris comme une ville étrangère dont on ne connaîtrait pas les codes, où chaque policier est une menace, où les habitants sont hostiles, pleins de morgue, difficiles d’accès ?"
"Des HLM de grande banlieue aux immeubles haussmanniens du centre, des MacDo aux immeubles de bureau, des centres d’hébergement d’urgence aux wagons de RER, c’est bien ma ville que j’ai filmée, parfois au coin de chez moi, mais sous un angle radicalement différent. L’autre dans le film, c’est nous : le travailleur pressé qui commande son Burger, le passant bousculé qui peste contre les livreurs à vélo, la fonctionnaire qui se tient face à Souleymane."
Boris Lojkine a voulu partir d’une base documentaire solide. Avec Aline Dalbis, une ancienne documentariste devenue directrice de casting, il est donc allé à la rencontre des livreurs : "Ils nous ont raconté les coulisses de leur travail : les démêlés avec leurs titulaires de compte, les arnaques dont ils avaient été victimes, les relations avec les clients ; ils nous ont parlé de leurs difficultés pour se loger, et des rapports avec leurs camarades livreurs, les collègues qui ne sont pas forcément des amis."
"Dans tous leurs récits, la question des papiers avait une place à part. Je l’ai vu notamment avec les Guinéens. Presque tous étaient ou avaient été demandeurs d’asile, et cette demande les obsédait, car avoir l’asile peut radicalement changer leur vie. Le drame, pour un livreur, ce n’est plus de se faire voler son vélo comme dans Le Voleur de Bicyclette (tu te fais voler ton vélo, tu en rachètes un le lendemain à Barbès). Le drame, c’est d’échouer à l’entretien de demande d’asile", se souvient le metteur en scène.
À l’image, Boris Lojkine a choisi de travailler avec Tristan Galand, jeune chef opérateur belge qui possède une double expérience de cinéma de fiction et documentaire. Le cinéaste précise : "Je voulais quelqu’un qui soit capable, pour certaines scènes, d’être seul à l’image, de cadrer et pointer en même temps et d’improviser lui-même des solutions de lumière tout en maintenant une direction esthétique forte."
"Le parti pris du film étant d’adapter le dispositif de cinéma au réel et non l’inverse, nous avons passé beaucoup de temps à chercher des décors qui nécessitaient peu ou pas d’intervention à la lumière et qui correspondaient à l’esthétique choisie pour le film : un Paris aux couleurs saturées avec des ruptures fortes dans les teintes."
Boris Lojkine voulait faire un film trépidant. Il a alors mis en œuvre une dramaturgie plus proche du thriller que de la chronique sociale, et qui se déroule sur une durée courte : "Tout au long de cette écriture, je pensais à deux films roumains qui m’ont marqué : 4 Mois, 3 Semaines, 2 Jours et La Mort de Dante Lazarescu. Tous deux racontent par le menu, minute après minute, les efforts d’un personnage qui se débat comme une mouche dans un bocal, en proie à un système qui l’oppresse. Comme Souleymane."
"Durant ces deux jours où il devrait se reposer avant son entretien, il n’a pas une minute de répit. Il court, il essaie de régler les problèmes qui s’accumulent, aux prises avec le système sans pitié d’une société européenne que nous croyons douce, mais qui est terrible pour ceux qui n’en sont pas citoyens."
Presque tous les acteurs du film sont des non-professionnels sans aucune expérience de jeu. Avec Aline Dalbis, Boris Lojkine a réalisé un long casting sauvage, arpentant les rues de Paris à la rencontre des livreurs. Le metteur en scène se rappelle : "Nous avons plongé dans la communauté guinéenne et c’est finalement à Amiens, par l’intermédiaire d’une association, que nous avons rencontré Abou Sangare, un jeune de 23 ans arrivé en France sept ans auparavant, alors qu’il était encore mineur. Son visage, sa parole, l’intensité de sa présence à la caméra nous ont d’emblée saisis. C’était lui."
Il n’y a pas de musique dans L’Histoire de Souleymane. Une volonté de Boris Lojkine, qui souhaitait faire un film sans artifices : "Non pour enfermer le film dans une esthétique documentaire, mais parce que je voulais jouer à fond la partition sonore de la ville, les klaxons et les sirènes, le fracas des RER, le rugissement des moteurs."
"L’absence de musique nous a obligés à être plus radicaux au montage : pas de place pour des moments creux, jolis, paisibles. On avance, collés à Souleymane, en apnée, sans répit, jusqu’à la scène finale qui nous enferme dans le petit bureau nu de l’Ofpra."
Nina Meurisse avait déjà tourné sous la direction de Boris Lojkine dans Camille, où la comédienne jouait le rôle-titre, une jeune photojournaliste se rendant en Centrafrique couvrir la guerre civile qui se prépare.
Pour filmer le vélo, Boris Lojkine a utilisé d’autres vélos (la seule solution pour se glisser dans la circulation) : "Un vélo pour l’image, un autre pour le son. Moi-même le plus souvent, je conduisais le vélo son, pour rester en prise avec le tournage. Je voulais rester léger pour me glisser dans la ville. Ne pas arrêter la vie. Insérer le dispositif de cinéma dans le réel. Et amener le maximum de réel dans la fiction."
"Même les scènes de dialogues complexes, je les ai voulues au milieu de la vie de la ville : dans le RER, au sein de la circulation, mêlées à la foule, au cœur du chaudron bouillonnant. Mon ingénieur du son (Marc-Olivier Brullé, avec qui je collabore pour la troisième fois) a dû inventer des dispositifs de prise de son inédits pour relever les défis que représentait ce tournage au milieu de la cacophonie de la ville."