The film begins with the silhouettes of soldiers being ordered to stand in the sun as an endurance test. It is a recollection of Adjudant-Chef Galoup (Denis Lavant) from his home in Marseille, where he is writing his memoirs. He remembers the heat of Djibouti, where he led his section of men under the command of Commandant Bruno Forestier (Michel Subor). We see numerous training scenes, including assault courses and the securing of buildings. Much of the reminiscence has a balletic quality; many of these reminiscences are set against a backdrop of the traditional, local Djibouti life. Galoup has a beautiful young local girlfriend and they often go out dancing.

Galoup says of Forestier: I admired him without knowing why. He retains a wristband with the word Bruno. Galoup envies many things in Forestier, including his clear affection from the men. However, they happily socialise together, playing chess and snooker.

One day, Gilles Sentain (Grégoire Colin) joins Galoup's section. Gilles' physical beauty, social skills, and fortitude make Galoup envious. Repressed homosexual feelings from Galoup are suggested. He swears to destroy Sentain.

When Sentain hands a canteen of water to another soldier who is being punished by being ordered to dig a large hole in the heat of the day, Galoup chastises Sentain and knocks the water from his hand. Sentain strikes Galoup, who retaliates by taking Sentain into the desert and leaving him to walk back to the base alone. However Sentain does not return because Galoup has tampered with his compass, and the soldier consequently becomes lost. When Sentain fails to return, he is assumed to have deserted.

Sentain collapses in the arid salt flats. His compass is spotted by fellow legionnaires at a sale of local salt-encrusted novelties and is believed to prove Sentain is dead. However, Sentain is found by tribespeople who place him on a bus where he is looked after.

However, on the assumption that Galoup has either killed or tried to kill Sentain, Galoup is sent back to France by his commander for a court martial. It ends his career in the Foreign Legion, his only real love. We see him make his bed in the immaculate military manner, then lie on top clutching a pistol. The final scene is Galoup back at a night club in Djibouti, engaging in a lively acrobatic solo dance to "The Rhythm of the Night"