Victor joins the French Foreign Legion, along with his faithful valet, Rake. His company is attacked while escorting a caravan. The survivors join a battalion stationed in southern Algeria. His new commander is Major Doyle, who becomes jealous when Cigarette, a cafe singer, loses her heart to Victor. However, Victor and a refined visiting Englishwoman, Lady Venetia, fall in love. Cigarette finds out and is heartbroken. Doyle learns about Cigarette's true feelings. Meanwhile, a carving of a horse created by Victor leads to Lady Venetia discovering from her uncle, Lord Seraph, that a certain English officer left England due to a scandal. It turns out that the officer was shielding his younger brother. The brother later met with a fatal accident, but lived long enough to exonerate Victor. When Arab unrest threatens to erupt into open conflict, Doyle is ordered to prevent it. He sends Victor off on suicidal mission after suicidal mission to try to get rid of his rival, but the sergeant returns each time unscathed. Then Doyle orders him to take 20 men to man an isolated fort, where they are surrounded by a vastly larger Arab force. Cigarette learns what Doyle is doing and rides out into the desert. Doyle repents his actions and leads a relief force, but Victor can only watch helplessly as they march into a trap. They manage to hold out until nightfall ends the fighting temporarily. Victor sneaks in, disguised as an Arab, and reports to Doyle. When Doyle tells him that reinforcements could arrive at noon the next day, Victor volunteers to buy time with a ploy of his own devising. Victor goes to see Sidi-Ben Youssiff, the Arab leader, who turns out to have been a classmate at Oxford. Victor tells him that there is a British force to the Arabs' rear. Sidi-Ben Youssiff scoffs at the idea that the French would allow British troops in their territory, but Victor persuades him to send scouts to check. They find nothing, but before Sidi-Ben Youssiff can execute Victor, French chasseurs attack the Arab camp, routing the Arabs and ending the revolt. During the fighting, Cigarette is shot and dies in Victor's arms. Afterward, Victor is shown in civilian clothes holding Lady Venetia's hand during a ceremony honoring Cigarette.
Writing for The Spectator in 1936, Graham Greene gave the film a good review, specifically praising the film's climax as "superb". Despite some mocking of the British Board of Film Censors over its award of an "Adult Certificate" for what amounted to "six chaste, sandy kisses", Greene approved of the film's acting and specifically lauded the acting of Colbert for whose admiration Greene noted was unbounded. In The New York Times review, Frank Nugent called Under Two Flags a "spirited and colorful revival" that "continues to be a stirring and romantic fable". His only qualm was that "Miss Colbert, gracious actress though she is, was not particularly fitted for the rôle of Cigarette, lacking somehow the whole-hearted "child of nature" qualities Ouida imagined." The film was a success at the box office.
