A cafe singer and an English lady fall in love with a French foreign legion sergeant, who is placed in danger by a colonel, who loves the singer.
In Algeria a company is ordered to march, and Cigarette (Claudette Colbert) complains to Major Doyle (Victor McLaglen) for her father. Doyle says she puts him off; but she promises a kiss, and he orders them back because relief has not arrived. Doyle finds men half buried dead in the desert. Corporal Victor (Ronald Coleman) and his men find crates of food and wine. Doyle commends Victor. Cigarette welcomes Victor to her cafe; but he drinks his own cognac. She sings; but he carries her, and she throws a knife. Doyle makes Victor a sergeant and sends him to spy in the market. Cigarette for an Arab sells Captain Menzies (Nigel Bruce) one horse as two. Victor and Cigarette race, and he wins a kiss. She rides off, and Victor pulls her off her horse. He apologizes, and she kisses him. Doyle looks for them, but they walk back.
Doyle meets Lady Venetia Cunningham (Rosalind Russell) and shows her his men and their carvings; Venetia meets Victor. Sergeant Victor sees her waltzing with Doyle. Victor gets in and gives Venetia his carved horse. They escape to an Arab town, while Cigarette waits and cries after her father laughs at her. Victor and Venetia meet in the desert, and he kisses her. Arab chief Ben Hamidon is killed for cooperating with the French. Doyle is ordered to move against the rebellion. Victor learns that Venetia's uncle is there. Cigarette asks Victor where he has been. Victor asks Venetia for the horse carving, saying England would mean prison for him. Cigarette sees Victor kiss Venetia. Doyle tells Cigarette that he is a colonel now, but she cries.
Doyle leads his men out to Fort Ain Sefra. Venetia's uncle finds the horse and tells Venetia that Victor was shielding his brother but has been cleared. Doyle sends Victor out on a fourth dangerous assignment, while Victor says he keeps coming back "like a bad penny." Cigarette learns that Doyle is trying to get Victor killed and tells Venetia he is not coming back, saying she loves him better. Venetia challenges her to save him. Doyle orders his men to relieve Victor, who sees they are being trapped. Many are killed. Doyle is shot and bandaged. More Arabs arrive. Cigarette approaches, sees, and rides for help. Doyle joins Victor in the fort. Victor volunteers to gain time; dressed as an Arab, he goes to Sidi Ben Youssiff, whom he knew at Oxford. Victor warns him of British troops and advises peace. In the desert at night Cigarette finds a French battalion. Victor admits he lied, but the Arabs are attacked. Victor sees Cigarette shot, and she dies in his arms. In the final scene Cigarette is honored as Victor and Venetia hold hands.
This romantic adventure has two European women among hundreds of men falling for the same man in the historical context of French colonialism imposed by military force on resisting Arabs.