C'est la première fois que les deux actrices hispaniques se retrouvent sur le même écran. Une rencontre très attendu, même de la part des deux stars qui ne le cachent pas : " cette alchimie qu'il y a eu entre nous, qui existait déjà à la ville et qui, je crois, transparaît vraiment à l'écran ! " confie Salma Hayek.
Les réalisateurs norvégiens sont tous deux issu de la pub, ils ont réalisé plus de 300 spots télévisés. Amis depuis l'enfance ils réalisent avec Bandidas leur premier long-métrage pour le cinéma.
Les réalisateurs travaillent avec Luc Besson depuis plusieurs années sous le Label DOG Production (une branche d'EuropaCorp). Ils avaient un projet de long-métrage : The Lake. Mais Luc Besson préféra leur confier Bandidas.
Pendant la pré-production de Bandidas, Luc Besson demanda aux deux réalisateurs de convaincre Salma Hayek et Penélope Cruz de faire le film. Ils devaient tourner une vidéo de présentation dans laquelle ils devaient se mettre en scène. "C'est probablement la pire chose que Luc ait pu nous demander ! confie Joachim Roenning l'un des réalisateurs.
L'équipe de Bandidas n'a pas fait les choses à moitié : une grande partie du film est en effet tournée dans l'Etat de Durango, connu pour avoir accueilli les caravanes de nombreux westerns "culte". Des films comme White Feather avec Robert Wagner, Les Voleurs de trains et Les Géants de l'ouest avec John Wayne, ou plus récemment Blueberry, l'expérience secrète de Jan Kounen ont été tournés sur ce site de légende.
Parmi les décors construits pour Bandidas, le village de Santa Rita se dresse sur des terres hantées par le souvenir d'une légende du western : John Wayne, qui acheta en 1969 un ranch dans lequel il fit construire la réplique d'une ville du Far West.
L'équipe de Bandidas a choisi la ville minière de Real De Catorce, perchée au coeur de la montagne. Pour y accéder, une seule option : la traversée du tunnel Ogarrio, qui débouche sur le bassin de mines d'argent entourant cette ville fantôme, qui avait déjà accueilli le tournage du Le Mexicain, avec Brad Pitt et Julia Roberts. Un triangle désertique, un pays de pierres et de lacs que ne traverse aucune route et dans lequel toute communication radio est immédiatement interropue !
Thierry Arbogast, directeur de la photographie, est un des collaborateur fétiche de Luc Besson. Il est l'un des chefs opérateurs français les plus estimés de la profession. Il compte trois César à son actif et une filmographie prestigieuse, notamment une collaboration avec Brian De Palma pour Femme Fatale. Bandidas est son premier western.
Eric Serra, plusieurs fois récompensé, est aux côtés de Luc Besson depuis ses débuts dans le cinéma. Pour Bandidas son influence pour la musique ethnique lui sera indispensable : "je me suis beaucoup amusé à faire des choses pseudo traditionnelles, notamment dans l'esprit des groupes de Mariachi".