In 1940, France is fighting a war for survival and recalls many of its legions from Africa, leaving several outposts vulnerable. In the Sudan, rebellious Tuareg tribes attack a French patrol from the fort at Timbuktu and kill the commander. Later, after Col. Charles Dufort, accompanied by his wife Natalie, arrives to take over, he learns that a holy man, Mahomet Adani, is believed to be the instigator of the local attacks. Meanwhile, in the native quarters of the town, trader Mike Conway arranges to deliver guns he has stolen from the French to the rebels in Bou Djebeha. As Charles has ordered that no one can leave Timbuktu, Mike decides to play one group against the other and offers to find Adani for him, in exchange for an exit permit. Charles agrees and Mike's caravan sets out on horseback across the desert, followed by a patrol led by Charles. Natalie and Jeanne Marat, the wife of a lieutenant on duty at their destination, accompany the patrol. After Suleyman, one of Adani's men, tricks Mike and makes off with most of the guns, Mike reveals that the cases actually contained sewing machines. Mike then advises Charles that Adani will retaliate when he discovers that he has been duped, and Charles sends Capt. Girard on ahead to alert the garrison at Bou Djebeha. However, after resuming their trek, they come upon Girard's dead body staked out in the sand, but arrive safely at the fort. There, Mike dresses as a native and locates Suleyman, who takes him to meet the Emir. Mike then delivers the guns and after being paid in gold coin, tells the Emir that Suleyman had tried to double-cross him. When Mike conducts a demonstration of a machine gun, the Emir uses it to kill Suleyman, then reveals that he is holding Adani, a pacifist, prisoner and intends to initiate a Holy War. After Mike meets Natalie at the Emir's nearby palace, she tells her husband that she does not want to see Mike again as she likes the adventurer and fears his charm. After sending a letter to Dufort asking that he not attack the Emir until he can rescue Adani, Mike then convinces the Emir that he is in love with Natalie and an enemy of her husband. When Charles and Natalie are invited to dinner at the Emir's palace, Mike and Natalie secretly develop their romance and are seen kissing by the Emir. Lt. Marat joins up with Mike in his attempt to rescue Adani and prevent the Emir from using him as a martyr. While the Emir thinks that Mike is keeping a rendezvous with Natalie, Mike and Marat are actually freeing Adani. However, Marat is captured and, later, Mike sees him staked out in the sand tortured by poisonous spiders and can do nothing to help while Marat is bitten and dies. The Emir is convinced that Mike knows where Adani is hidden and kidnaps Natalie to force him to talk. Mike tells the Emir he will reveal Adani's whereabouts after Natalie is returned to her husband and he receives her husband's ring, which he will recognize, as proof. However, when Charles refuses to hand over the ring, changes clothes with a Tuareg prisoner and sets out to find Mike, Natalie realizes that he is performing a noble act. The Emir's men return, followed by Charles, who finds Mike staked out in the sand undergoing a version of the spider torture, but is able to rescue him. When the Emir discovers Mike is gone, he leaves for Timbuktu. However, Mike has hidden Adani in one of the gun carts the Emir is taking with him, so he and Charles hijack it and enter Timbuktu as one of the Emir's caravan. Once inside, they attempt to get Adani to a mosque tower from which he can warn his faithful followers of the Emir's plans. While Charles holds off the Emir's men at gunpoint, Mike takes the holy man to the tower. However, Charles is killed by the Emir, but Mike avenges his death by shooting the Emir. Adani addresses his people and tells them that the Emir was a traitor who wanted to become a tyrant over them and implores them to seek independence with honor. When reinforcements arrive, Mike states that Charles was a great soldier. Later, he and Natalie ride off together.