Једине плаћеничке формације које су се у континуитету задржале у готово два и по века јесу француска Легија странаца и британске Гурке. Првобитно Легија странаца организована је у току француске револуције, и имала је мало додирних тачака са оружаном формацијом из каснијег периода. Све је почело одлуком француске законодавне скупштине од 1. августа 1792. године, о стварању слободне Легије странаца (Legion franche entrage), и то као здружене јединице три рода војске, која се попуњавала бегунцима из инвазионих армија. Тако је већ 4. септембра исте године створена Германска легија. За њом су следеле и друге легије, формиране углавном од странаца – револуционара који су одлучили да се боре за идеале француске револуције: „Пољска, Грчка, Немачка, Дунавска легија, Баварски батаљон“. После мира у Амијену, 1802. године, стране трупе таквог карактера већином су расформиране, а 1804. године распоређене по француским пуковима.
Од тада је прошло готово тридесет година, а у Француској је на власти био поново краљ. Овог пута Луј Филип, који законом од 10. марта 1831. године, формирао Легију странаца сасвим другачијег карактера и намене од претходне. Ова формација је одмах упућена у освајање Алжира, а затим бива уступљена на „испомоћ“ Шпанији, где помаже у гушењу устанка Карлиста од 1835. године до 1838. године. Од 5000 послатих легионара, преживело их је само 500. У међувремену, 16. децембра 1835. године, створена је, трећа по реду, нова Легија странаца, која се одржала све до данас, и која је наставила са даљим освајањем Алжира и Северне Африке.
Од тада па све до наших дана, њене јединице имаће, као основни задатак, ширење и очување колонијалних поседа по сваку цену, и обично ће добијате оне прљаве послове које нису желеле или нису могле, да обављају трупе произашле из опште војне обавезе. Од Мексика до Аустрије, од Алжира до Мадагаскара и Индокине, пут легионара биће обележен крвавим биткама, али и насиљем које неизбежно иде уз то. Било је јасно да таква Легија странаца, нема више ништа заједничко са узвишеним идеалима легије из револуционарних дана. Сада је она постала уточиште за авантуристе, беспосличаре и криминалце који су ступањем у њене редове, лако могли прикрити свој идентитет, као и професионалних војника, који нису знали ништа друго да раде.
Легија странаца је, како су године пролазиле, имала бројне реорганизације и попуњавала се стално новим људством. До краја 19. века била је константно упослена, учествовала је у борбама у Шпанији и на Криму, после чега је подвргнута детаљној реорганизацији. Тако је 1855. године, главна база Легије странаца пребачена у Алжир, где је попуњена великим бројем Швајцараца „два пука од по два батаљона“. Од 1863. године до 1866. године, осам батаљона Легије чинило је француски експедициони корпус, који је имао задатак очувања и проширења француских колонијалних интереса у Мексику. Међутим у борбама са мексичким устаницима, претрпили су велике губитке, па су се 1867. године повукли необављеног посла.
Пред крај 19. века два батљона Легије послата су на Далеки исток, у Анам, Тонкин (сада Вијетнам) и на Формозу (Тајван), опет као крвави мисионари колонијалних интереса. У току Првог светског рата, кроз главну базу легије у Сиди-бел-Абесу, на територији Алжира, прошло је око 53000 легионара. Многобројне крваве битке, проредиле су редове легионара. Од 14000 Швајцараца, погинуло је њих 9000. Непосредно после рата, истањени редови Легије странаца, „добили су нову дозу свежег људства“. То су били руски емигранти и демобилисани припадници поражене немачке Царске војске. Током тридесетих година прошлог века, у пет пешадијских и једном коњичком пуку, било је око 30000 легионара од Африке преко Индокине и Леванта.
У првим годинама Другог светског рата, већи део Легије странаца пришао је јединицама француског генерала Де Гола, који се са својим сарадницима налазио у Великој Британији.
Легија се током тог рата борила у Африци, Италији, Француској и Немачкој. Процењује се, да је у овом рату погинуло око 40000 легинара. По завршетку рата, састав Легије странаца чинили су Немци у око 70 процената, углавним из Ромеловог Афричког корпуса. То су дакле, били управо они Немци, који су се жестоко борили против Легије странаца у Северној Африци. Али како бива у Легији странаца, дојучерашњи љути непријатељи, за легионарску плату, преко ноћи постају саборци.
Следеће ратно поприште била је Индокина. До 1954. године, у борбама са ослободилачким снагама „Вијетмина“, посебно на тзв. „Колонијалном путу број 4“, погинуло је 12019 припадника Легије странаца. Преломни моменат у рату, представљала је чувена битка за Дијен Бијен Фу.
Битка за Дијен Бијен Фу трајала је од 13. марта до 7. маја 1954. године, у којој је учествовало преко 14000 француских војника, укључујући и осам легионарских батаљона. Губици легионара износили су 1500 погинулих, а много више је рањених припадника.
Алжир је био последњи велики полигон за доказивање „проклетника“ из Легије странаца. Били су изгубљени критеријуми цивилизованог понашања, па је на том полигону све било дозвољено. Уосталом, убијање је био њихов занат, оличено у старој легионарској пароли: “ Живео рат, живела смрт, живео проклети плаћеник“!
Међутим, отпор народа Алжира био је много снажнији од легионарског напора. Алжир је званичо постао независан 3. јула 1962. године. Почело се размишљати о новом седишту легионара после Алжира.
У том тренутку француска Легија странаца имала је 18000 војника, од чијег броја око 40 посто били су Немци. Маја 1962. године, почиње велика селидба Легије странаца из Алжира. Делови Легије, пребачени су на различите и међусобно прилично удаљене дестинације: на Мадагаскар, у Џибути и Француску Гијану. Од октобра исте године матични логор легионара постаје Ла Деманд недалеко од Обања. Овакав распоред, био је делом због чињенице да тадашњи председник Француске Де Гол, никада није опрости Легији побуну из 1961. године.
Тад се први падобрански пук Легије, као језгро најтврђих легионара у такозваном „алжирском пучу“, ставио на страну побуњених и крајње десно оријентисаних генерала, који су за циљ имали рушење Де Гола са власти и задржавања Алжира у статусу колоније. По краху пуча, пук је расформиран а улога Легије је доста редукована. Међутим, њена улога ће поново доћи до изражаја током шездесетих и седамдесетих година 20. века. Још увек је било посла за легионаре.
Посебно је за тај крвави посао, била идеална Африка од Чада до Заира и даље диљем континента, иако Легија неће више достићи „свој колонијални сјај“ који је имала у прошлости.
После Алжира, легија је од 1964. године, била присутна у Чаду, Сомалији, Заиру, Габону, Малагасију, Либану и другде. Легионари су учествовали у следећим војним интервенцијама и операцијама:
Џибути 1976. године, операција „Такауд“ (Чад 1978. године), „Леопард“ (Колвези, 1978. године), „Баракуда“ (Централна Африка), „Епаулард“ (Либан, 1982. године у саставу мултинационалних снага), „Манта“ (Чад 1983. године), „Епривер“ (Чад, 1987. године), „Рекуин“ (Габон, 1990. године), Руанда (1990. године), „Пустињска олуја“ (Ирак 1991. године), „Баумиер“ (Заир, 1991. године), „Вердиер“ (Того, 1991. године), „Годор“ (Џибути, 1991. године), „Обнова наде“ (Сомалија, 1993. године), „Тиркиз“ (Руанда, 1995. године), бивша СФРЈ, потом БиХ у саставу УНПРОФОР (1991. године до 1995. године), а затим ИФОР, СФОР, ЕУФОР, потом НАТО агресија на СРЈ 1999. године и сада у саставу КФОР, а онда Авганистан од 2001. године.
Иако су на простор БиХ ушли у саставу међународних снага УНПРОФОР, легионари су доживели и нешто, чему се сигурно, нису надали.То се односи на срамно заробљавање, од стране јединица ВРС у пролеће 1995. године. Тад су их војници ВРС, ефикасно разоружали и заробили, у знак „одмазде“ због НАТО бомбардовања положаја ВРС. Ово заробљавање, тешко им је пало. У БиХ су срушене многе предрасуде и заблуде, многи митови заглибили су се у блато, које је поприлично, чини се упрскало и бљештаве униформе и сјајну прошлост и славу француске Легије странаца.
Негде, крајем деведесетих година прошлог века плата легионара зависно од стажа и чина, кретала се у просеку око 2000 тадашњих долара. Ратни додатак, износио је од 100 до 200 долара дневно. Данас та плата износи у просеку око 1380 евра. Годишње се у Легију странаца прими од 1000 до 1600 људи (иако се пријављује знатно више). До сад (јул 2023. године), регрутовано је 1600 људи.
Мотиви за улазак у Легију су различити, али идеали, авантуризам и опседнутост војним позивом учествују са 20 посто, док је у 80 посто неки други разлог. Висина пензије легионара, износи око половине просечне плате, али је треба дочекати жив и са неоштећеним здрављем.
Најмање ангажовање је на пет година, али може обострано бити поништено у пробном периоду од шест месеци, после тог уговор се не може прекинути све до истека истог. Право на пензију, легионар стиче после 15 година службе.
Данас Легија странаца броји око 8000 људи, организованих у осам пукова, који чине основно језгро француских снага за брзе интервенције и узимају учешћа у разним интервенцијама широм света.
У читавој причи о Легији странаца, посебно је занимљива чињеница да је увек било људи који су из ових или оних разлога, често желели да ступе у њене редове и постану како је већина њих то замишљала – правим војничинама. Захваљујући баш њима Легија је до сад, успевала да преживи сва искушења политичког, економског и војног карактера. За све њих, Легија је њихова једина отаџбина: „Legiо Patria Nostra“.