The next scene opens at Saida in French Morocco, the clearing station for the desert forts, where Beau has been reunited with Digby in the legionnaires' training post for a five-year stint. The camera follows the stiff-backed form of the commanding officer, the sadistic, tyrannical, scar-faced and brutal Russian Sgt. Markoff, as new recruits are marched into the compound.

The trio is brought together in the Foreign Legion. One of the new enlistees in line is John ("the third robber") - who is immediately threatened by Markoff for having lived a privileged, soft life: "Never have done a day's work in your life, have you?...I'll manicure those [hands] before we're through." Another one of the recruits is the weasly Rasinoff (J. Carrol Naish), who has a reputation of being a thief. Determined to discipline the assembled men, Markoff speaks to them in tough tones:

Discipline makes the strength of armies. It is necessary that superiors obtain from their subordinates immediate obedience without murmuring. Discipline will be firm but it will also be fatherly. Officers must use psychology when dealing with men. Any questions about the regulations? I am Sgt. Markoff. I make soldiers out of scum like you, and I don't do it gently. You're the sloppiest looking lot I've ever seen. It's up to me to prevent you from becoming a disgrace to the regiment. And I will prevent that if I have to kill half of you with work. But the half that lives will be soldiers - I promise you.

Noted for being a cruel taskmaster, Markoff is reprimanded by his own commanding officer for being too strict: "They're men. They have rights, guaranteed by the regulations...You're a good soldier, Markoff. But I doubt if you're a good Sergeant. If you're not, you won't last long in the Legion. Watch your step or I'll break you!" One of the recruits has heard of the Sergeant's reputation: "He's a madman. He was expelled from the Siberian penal colony for cruelty. Then he entered the Legion and rose from the ranks."

Rasinoff overhears the Geste brothers mention in passing that they are "high-class jewel thieves." He also eavesdrops as each of the brothers boast about how they possess the stolen Blue Water sapphire - in particular, Beau plans to retire in Paris after selling it: "I've got it. I intend to sell it for 30,000 pounds sometime in the future and live a life of ease in Paris surrounded by whiskey, ladies and laughter." John tops him with his own fantasy: "The great sapphire is in my possession and as soon as I can arrange to sell it, I am going to the South Seas, buy a plantation, and start trading in copper."

"Another night...a month later...a fourth jewel thief...uninvited." Attempting to rob John of his money belt during his sleep, Rasinoff is caught red-handed and roughed-up by the other legionnaires in the barracks. The commotion draws Sgt. Markoff to their quarters and he interrupts the punishment being administered to the thief. During questioning, Rasinoff informs Markoff that the brothers have a stolen, precious jewel: "They have a great jewel worth 30,000 pounds that they stole...They are brothers and they're waiting for a chance to sell it. But he [Beau] is the leader. He carries it. I've watched him." After learning of the jewel's existence, Markoff also wants to possess it and schemes to separate the brothers after their training period is over:

Markoff: Make sure you're telling me the truth.
Rasinoff: I am. I am!
Markoff: You know, I think I can help you get that jewel.
Rasinoff: (disingenuously) Well, that's what I hoped.
Markoff: (sarcastically) I'm sure you did. In a week, we go to relieve the garrison at Fort Zinderneuf. It can be arranged there.
Rasinoff: But there are three of them and two friends.
Markoff: Some of the company go to Fort Tokotu for mounted infantry training. It can be arranged. And if there's no jewel, you'll get a wooden jewel box. I promise you.
Rasinoff: But he has it, I'm sure of it.

At the end of the legionnaires' training, the men are instructed to fulfill the chivalrous, honorable tradition of the French Legion: "You are now soldiers in the service of France. We are here in the desert as guardians of twenty millions of natives. They look to us for the protection and justice that is the tradition of the Foreign Legion. Yours is a high duty and a hard one. The odds are great. It is our allegiance to France and our debt to civilization to uphold that tradition." Sgt. Markoff breaks up the trio by sending Digby to the remote desert post at Fort Tokotu, and Beau and John are dispatched to Fort Zinderneuf with the Sergeant.

But months later at Zinderneuf - it has become a living hell. The men complain about their harsh treatment - it would be even worse if the ailing and feverish Lieutenant Martin (Harvey Stephens) died, placing Sgt. Markoff directly in command. Although two deserters from the fort, Renault (Arthur Aylesworth) and Renouf (Henry Brandon) have been captured by Arab scouts and brought back, one of the angry legionnaires Schwartz (Albert Dekker) contemplates killing Markoff and deserting the Legion. To teach a lesson to the entire company, the Sergeant mercilessly makes an example of the two men. He threatens to punish the debilitated, half-dead deserters in front of the others by forcing them to re-enter the searing heat of the desert and face certain death:

The punishment for desertion is death by the firing squad. But I'm going to be merciful. You can escape again...I insist that you escape!...(To the scouts) Drive them out where you found them. And keep them away from the oasis. (Turning back with a scowl toward the legionnaires) Any more of you want to desert? If you do, you can go now. I won't stop you. Later, you may wish you'd taken my offer, I promise you.

Before dying, Lieutenant Martin speaks to Markoff about his replacement, and encourages his second-in-command to ease up on the men: "When I was a little boy, I thought soldiers always died in battles. I didn't know there were so many soldiers and so few battles and so many fevers. Get word to Beaujolais at Tokotu. Have him send another officer. You'll be in command until then...The men must be led, not driven. Remember, you'll answer to the man who takes my place..." The Sergeant smiles villainously as he puts his ear to the now-silent Lieutenant's chest to listen for a heart-beat.

Now that he is officially in command, Markoff lives up to his cruel reputation as he addresses the men during a meal in the barracks:

Lieutenant Martin is dead. I am now in command. From this moment on, discipline at Fort Zinderneuf will be severe. I promise you!

Schwartz incites the men to rebellious mutiny:

Don't tell me he took your appetites away. He'll take more than that away before long...Markoff has been asking for it, and now he's gonna get it...You don't want to stay here and die like rats in a trap, do you? Will you let that madman squeeze every drop of blood out of ya, and drive you out in the desert like he did Renouf and Renault? Will ya? We are fifty against one. How long are you gonna keep on licking the boots that kick ya? Those stripes on a sleeve won't stop a rifle bullet. Let's get him now!

The majority of the men support Schwartz, but he is opposed by Maris (Stanley Andrews): "Hold it! Don't listen to him. You'll never get away with it." The two Geste brothers, led by a gallant and courageous Beau, persuasively resist Schwartz' plan of mutiny:

There'll be a flag flying out there in the morning that I swore to uphold. Armies of good men have died for it gladly. It's a battle flag and a flag of victory. I'm rather proud to be under it. And I wouldn't want to go out in the morning like you and know that I was going to be a traitor to it.

Voisin (Harold Huber), a turncoat spy, betrays the legionnaires and informs Markoff of the secret mutiny: "A mutiny in the morning on parade...The English brothers and Maris are faithful." Aware of the plot, Markoff - with Rasinoff's assistance - disarms the sentry, alerts the brothers and Maris to aid them, usurps the rebels' weapons, and then confronts the unarmed mutineers at gunpoint in the barracks:

The attempt at mutiny is over, my children. You bungled it so much it wasn't really a mutiny. But you'll be punished as though it were.

In the light of day, the soldiers are led out in marching pairs into the yard where they are given another lesson by the sadistic, stern commander:

And now, you scum! It's my turn. I'm going to give you a lesson in putting down an attempted mutiny that'll be the last thing you'll ever see. Maybe this will make you die happy. Markoff thanks you. When he's an officer and has the Legion of Honor, he'll think often of the stupid, blundering pigs that put him where he is.

Schwartz and Renoir (Harry Woods) are lined up with their backs to the gate - they are told: "The punishment for mutiny is death!" The Gestes are ordered to shoot the ringleaders: "These two pigs deserve to be first. And the honor of killing them belongs to the two most loyal men in the fort." After Beau refuses to carry out the command to kill unarmed men, Markoff turns his pistol on them and threatens to kill them. But news of an impending attack by a desert band of enemy Arabs interrupts the proceedings. Markoff orders the Arab scouts to go for relief to Fort Tokotu, and then commands all the men to take up arms and assume their defensive military posts against the assault.

During the rousing battle against overwhelming odds, the men - still dressed in their pajamas - valiantly hold back the attack as their French tri-color flag is raised. The tyrannical Sgt. Markoff exhorts his legionnaires: "Keep it up, you scum. Keep shooting! You'll get a chance yet to die with your boots on." In a closeup, he yells: "Now we've got something to fight under. Rapid fire, you scum, rapid fire! Ha, ha!" The Arab attack is momentarily repelled, and there is a break in the fighting for over three hours. The men change into their Foreign Legion uniforms. In a second wave of attack, some of the legionnaires are killed. The Sergeant props their corpses in every embrasure:

Everybody does his duty - and soon enough. Dead or alive. We'll make those Arabs think we got a thousand men. The rest of the bullets you stop won't hurt as much as that first one.