Založenie a prvé roky
Cudzinecká légia bola založená 10. marca 1831 za vlády francúzskeho kráľa Ľudovíta Filipa I. počas vojenských a koloniálnych konfliktov, ktoré v tom čase Francúzsko zažívalo. Primárnym dôvodom pre jej vznik bolo poskytnúť formáciu profesionálnych vojakov, ktorí by slúžili v koloniálnych vojnách, najmä v Alžírsku, a umožniť cudzím štátnym príslušníkom, aby sa stali súčasťou francúzskej armády.
Zakladateľom bol Maréchal Bugeaud, ktorý bol vtedy generálom a potreboval silu na udržanie francúzskej kontroly nad Alžírskom. Légia bola pôvodne zložená z dobrovoľníkov z rôznych krajín, ktorí boli prijímaní bez ohľadu na národnosť, jazyk, alebo pôvod. To malo byť atraktívne pre mužov, ktorí hľadali nový začiatok, často po neúspechoch v osobnom živote alebo v predchádzajúcich vojnách.
Počas 19. storočia sa Cudzinecká légia podieľala na mnohých kolonizačných vojenských operáciách po celom svete. Zúčastnila sa vojenských ťažení v Senegale (1849–1854), Indočíne (1858–1883), v Mexiku (1863–1867) a Tonkinu (1873–1885). Legionári bojovali v ťažkých podmienkach, od tropických lesov po púšte, pričom sa ich povesť nezlomných bojovníkov čoraz viac upevňovala.
V Francúzsko-pruskej vojne (1870–1871) bola Cudzinecká légia zapojená do obrany Francúzska pred pruskými vojskami. Po katastrofálnej porážke Francúzov a páde Paríža sa jednotky Cudzineckej légie podieľali na obranných operáciách, aj keď konečný výsledok vojny bol pre Francúzsko zdrcujúci. Po vojne sa zvýšil nábor do Légie, ktorá poskytovala možnosť pre mnohých vojakov, ktorí stratili svoju vlastnú krajinu alebo sa chceli ukryť pred následkami vojny.
Po vypuknutí prvej svetovej vojny sa Cudzinecká légia opäť zapojila do vojenských operácií, predovšetkým na západnom fronte. Počas bitky pri Verdune (1916) a bitky na Somme (1916) sa legionári vyznamenali nielen v náročných podmienkach zákopovej vojny, ale aj v bojoch, ktoré boli plné obrovských strát. Cudzinecká légia sa preslávila svojím odhodlaním a odolnosťou, pričom mnoho jej príslušníkov položilo životy. Na konci vojny Légia zaznamenala vysoké straty, ale jej povesť ako elitnej jednotky bola posilnená. V tomto období sa Légia stala symbolom statočnosti a bojovej zdatnosti.
Po prvej svetovej vojne Cudzinecká légia pokračovala v plnení rôznych misí v kolóniách, vrátane Franceskej Indočíny a Maroka. V roku 1925 sa zúčastnila Rifskej vojny v Maroku, kde bojovala proti povstaniu berberských kmeňov. Légia naďalej posilňovala svoju pozíciu v koloniálnych vojnách a v rokoch 1930 až 1939 sa jej príslušníci podieľali na pacifikácii v Sahare a Sredozemí.
Cudzinecká légia zohrala významnú úlohu aj v druhej svetovej vojne. Po páde Francúzska v 1940 bola väčšina francúzskych vojsk porazená nemeckou armádou. Napriek tomu sa niektoré jednotky Cudzineckej légie zapojili do francúzskeho odboja a pokračovali v bojoch na strane Spojencov. Po nemeckej okupácii a vytvorení Vichistického režimu, Légia poskytla dobrovoľníkov pre Francúzsku voľnú armádu generála de Gaulla, pričom niektorí príslušníci Légie bojovali aj v Afrike, Taliansku a Normandii. Neskôr sa Cudzinecká légia zúčastnila aj na bojoch na východnom fronte proti nemeckým vojskám.
Po druhej svetovej vojne
Po skončení druhej svetovej vojny sa Cudzinecká légia zúčastnila ďalších vojenských konfliktov v rôznych častiach sveta. Najvýznamnejšie z nich boli:
Vojna v Indočíne (1946–1954): Légia sa podieľala na francúzskom úsilí udržať kolóniu v Indočíne, kde v rokoch 1954 utrpela ťažkú porážku pri bitke pri Dien Bien Phu, ktorá viedla k ukončeniu francúzskej prítomnosti v tejto oblasti.
Alžírska vojna (1954–1962): Cudzinecká légia zohrala kľúčovú úlohu v Alžírskej vojne za nezávislosť, ktorá trvala od 1954 do 1962. Légia sa dostala do konfliktu s národným oslobodeneckým hnutím FLN (Front de Libération Nationale), pričom jej vojaci čelili guerillovým taktikám a brutálnym bojom. Po skončení vojny a uznaní nezávislosti Alžírska v roku 1962 bola Cudzinecká légia jednou z posledných jednotiek, ktoré opustili krajinu.
Postkoloniálna éra a súčasnosť
Po získaní nezávislosti Alžírska sa Cudzinecká légia presunula do ďalších francúzskych kolónií a oblastí. Zúčastnila sa vojenských operácií v Strednej Afrike, Kambodži, Pobreží Slonoviny, Vietname, Východnom Timore a v Somálsku. V súčasnosti je Cudzinecká légia naďalej súčasťou Francúzskej armády, vykonávajúc rôzne mierové a bojové misie na celom svete. Zúčastnila sa tiež operácií v Iraku a Afganistane a v bojoch proti terorizmu.
Cudzinecká légia je dnes považovaná za elitnú vojenskú jednotku, ktorá prijíma mužov z rôznych krajín a národností, pričom jej tradícia, disciplína a odhodlanie naďalej pokračujú.