"who'd been in the Foreign Legion"
Members of the Foreign Legion in ceremonial dress
GNU Free Documentation LicenseMembers of the Foreign Legion in ceremonial dress - Credit: David Monniaux, Wikimedia Commons

The French Foreign Legion, established in 1831, is a unit in the French Army open to both French citizens and foreign nationals.  At the time of the book, it was based in Algeria, then a French colony.

The legion is renowned for the arduousness of its training program, which is designed to stretch recruits to the utmost, both physically and psychologically.  Recruits are given new names, and any misdemeanours or crimes in their past are ignored, making the legion an attractive way of "starting over".