Frères du désert a été adapté du roman Les Quatre plumes blanches écrit par A.E.W. Mason. Cet ouvrage avait déjà été porté à l'écran par Zoltan Korda en 1939 et Terence Young en 1955.
Le tournage débuta au Maroc. De nombreux décors naturels furent choisis, dont celui des hautes montagnes de Fint et la ville de Ait Ben Hobdou, vieille de six cent ans, utilisée pour les extérieurs de la forteresse d'Abou Clea. Les dunes situées aux alentours de la ville de Merzouga servirent aux scènes se déroulant dans le désert.
Puis le tournage se poursuivit en Angleterre, dans des décors aussi variés que le Blenheim Palace, le château de Hyde Claire ainsi que l'intérieur de différents manoirs, témoins de l'ancienne grandeur de l'Angleterre.
Durant le tournage, les tempêtes de sable étaient une menace permanente. Pour se protéger de tels éléments naturels, il fallait filmer à partir de campements provisoires à chaque fois.
Le directeur de la photographie Robert Richardson a principalement filmé les scènes de désert face au soleil. Celui-ci s'explique : "En éclairant par derrière, j'ai pu obtenir un contraste saisissant entre personnages et paysage". "Cette technique permet de donner au film une atmosphère de qui-vive et de réalisme" confie le réalisateur.
Chef costumière, Ruth Myers devait veiller à l'authenticité des uniformes anglais, des robes victoriennes portées par Kate Hudson et des costumes revêtus par les rebelles musulmans. Elle souhaitait, avant tout, à travers les vêtements exprimer la rencontre brutale entre rigidité victorienne et liberté africaine.