Pentru a putea pacifica colonia Algeria, regele Franței Ludovic Filip (1773-1850) avea nevoie de soldați căliți în luptă, dar de care, la nevoie, să se poată lipsi. El și-a împlinit această dorință creând o nouă unitate militară pe 10 martie 1831. Atunci, ministrul francez de război, mareșalul Nicolas Soult, a înfințat Legiunea Străină Franceză, precizând că aceasta nu trebuie folosită pe teritoriul continental al regatului.
Ofițerii Legiunii erau recrutați dintre veteranii armatei lui Napoleon, care, după Waterloo (1815), stăteau degeaba pe jumătate de soldă. Soldații de rând erau adunați din toată Europa, fiind adeseori vorba despre oameni disperați, care nu-și găseau pe nicăieri un loc de muncă sau care erau urmăriți de autorități.
În decurs de un an, efectivele Legiunii numărau 5 500 de ofițeri, subofițeri și legionari. Prima luptă la care a luat parte Legiunea a avut loc în aprilie 1832, când două batalioane alcătuite mai ales din soldați germani și elvețieni au luat cu asalt un sat de la est de Alger. De atunci, legionarii au luptat în sute de războaie și conflicte armate din toată lumea. Ei au fost prezenți la asediul Sevastopolului, în timpul Războiului Crimeii, și l-au sprijinit pe împăratul-marionetă Maximilian în timpul domniei sale tragice în Mexic.
Printre zonele de conflict africane în care au fost prezenți legionarii se numără Dahomey, Madagascar, Tunisia, Ciad, Liban și Algeria. De asemenea, au participat la Războiul din Vietnam, în Bosnia și la Primul Război din Golf.
De-a lungul anilor, Legiunea a avut în rândurile ei câteva nume celebre. Cel mai ilustru ofițer al Legiunii a fost Patrice de Mac-Mahon, care a activat ca legionar în anii 1843–1844, a condus apoi armata franceză spre marea victorie de la Magenta din 1859 și a ajuns, în final, președinte al celei de-a Treia Republici, în 1873. Doi alți membri ai Legiunii au devenit prim-miniștri ai Franței. Edouard Daladier a fost prim-ministru mai mulți ani, în anii 1930, iar Pierre Messmer a fost prim-ministru sub de Gaulle și Pompidou.
Astăzi, Legiunea se mândrește cu mercenari din circa 99 de țări, oameni duri, uneori infractori urmăriți de lege. Nu există francezi în Legiunea Străină, exceptându-i pe ofițeri. Această combinație între conducerea franceză și soldații străini a creat o forță de luptă formidabilă.
Astăzi, Legiunea Străină Franceză are un efectiv cuprins între 8.000 și 9.000 de oameni. În fiecare an, candidează la admitere circa 500 de inși, dar mai puțin de 10% sunt acceptați. Durata minimă a serviciului este de 5 ani, nu ți se permite să locuiești în afara cazărmii, iar căsătoria e interzisă până când promovezi la rangul de sergent sau dacă nu ai servit vreme de 9 ani.
