Quando nell'agosto 1830, Luigi Filippo d'Orleans salì al trono dei Borboni, il Corpo di Spedizione del Maresciallo De Bourmont, forte di 37.000 uomini, era già sbarcato sulla spiaggia di Sidi Ferruch e, il 5 luglio, si era impadronito di Algeri.
Ordinata dal re Carlo X per mettere fine alla pirateria barbaresca che da anni danneggiava il commercio marittimo nel Mediterraneo, questa spedizione militare fu vivamente criticata dalla stampa liberale già ostile al regime. La reazione di Carlo X che pensò di sopprimere, per decreto, la libertà di stampa, fu all'origine della rivoluzione del 25 luglio 1830 che lo costrinse a rifugiarsi in Inghilterra ed a cedere il trono a Luigi Filippo.
Il cambiamento di regime provocò la partenza di alcuni Ufficiali "legittimisti" rimasti fedeli a Carlo X, mentre altri furono sostituiti da militari più malleabili o meno compromessi con il precedente regime. Il Maresciallo De Bourmont venne così rimpiazzato dal Generale Clauzel alla testa della futura "Armee d'Afrique"
Il nuovo regime, pur contrario a proseguire in nord Africa una campagna alla quale si era dichiarato ostile solo alcune settimane prima, quando era ancora all'opposizione, ordinò al Gen. Clauzel di di occupare solo una parte del litorale di quella che sarebbe divenuta, in seguito, l'Algeria. Fù così che venne attuata la politica della cosidetta "occupazione limitata". In realtà, il neo costituito governo, temeva che il brusco rimpatrio di 37.000 uomini, tra i quali molti ancora fedeli a Carlo X, potesse minacciare la sua ancora precaria e instabile posizione.
Per poter continuare quella logorante campagna, che causava perdite quotidiane nei ranghi francesi senza che nessun vantaggio politico o militare venisse a compensarle, alcuni politici suggerirono a Luigi Filippo di far appello agli ex mercenari del "Reggimento di Hohenlohe" e della Guardia Svizzera per formare l'ossatura di un corpo di volontari stranieri, aperto anche a chi avesse dei problemi con la giustizia. I reduci delle numerose rivoluzioni o insurrezioni che divampavano in Europo avrebbero fornito un abbondante gettito di "mano d'opera" di prima scelta. L'idea piacque subito a Luigi Filippo che, pur di risparmiare sangue francese, decise di costituire una Legione di volontari stranieri che tuttavia, non avrebbe potuto "essere impiegata sxul territorio continentale del Reame".
Il 10 marzo 1831, l'idea di una Legione Straniera divenne realtà.
Il reclutamento delle truppe prese a marciare durante i primi sei mesi dalla legge. Nel settembre 1831, già cinque Battaglioni (1°,2° e 3° Btg. formato da tedeschi e svizzeri, 4° Btg. da spagnoli, 5° Btg. da italiani) vennero inviati oltremare, sotto il comando del Col. Stoffel, un Ufficiale svizzero che aveva servito in Francia per circa 30 anni e che aveva combattuto tra le fila dell'esercito di Napoleone in Spagna.
Questi primi Battaglioni sbarcarono ad Algeri, Orano e Bona. La Loro uniforme era quella della fanteria francese: pantaloni cremisi, marsina blu, un alto kepì nero ed un cappotto grigio ferro, portato arrotolato in una custodia sopra lo zaino. Unico distintivo della Legione era il "motivo" dei bottoni, recante il nome del reparto, che circondava una stella a cinque punte.
Mentre altri due Battaglioni, il 6° belga ed il 7° polacco, venivano formati in Francia, i Legionari in Algeria facevano conoscenza con le insidie della guerriglia. La strategia di quella guerra, infatti, era dettata dal nemico, su un tipo di terreno che favoriva particolarmente le imboscate e le incursioni, seguite da rapide manovre di sganciamento e ritirata.
Il 27 aprile 1832, il 1° e 3° Battaglione registravano il loro primo successo. Quel giorno assalirono gli avamposti che difendevano il grande villaggio di Maison Carrè ad alcune miglia ad est di Algeri. Questo gesto, valse alla Legione la sua prima bandiera, consegnata al suo nuovo comandante, il Col. Combe, recante la scritta "Il Re dei Francesi alla Legione Straniera".
Nell'ottobre 1832, dopo aver ricevuto i suoi ultimi due Battaglioni, la Legione contava una forza di 5.538 effettivi, tra Ufficiali, Sottufficiali e Legionari

Proprio in questo periodo si scatenava l'opposizione araba, guidata dal giovane e coraggioso emiro di Mascara, Abd-el-Kader. l'11 novembre 1832, egli giungeva alle porte di Orano con circa 3.000 cavalieri arabi.
La battaglia fu ingaggiata subito: la prima carica degli arabi fu fermata sul pendio del Djebel Tafaraouini, dominato dal piccolo "marabout" Sidi Chabel. I francesi organizzarono un contrattacco immediato: sulla destra c'erano i Cacciatori, e sulla sinistra i Legionari del 4° Battaglione. Questo reparto era composto da spagnoli, molti dei quali avevano fatto esperienza di guerriglia nella penisola Iberica, contro Napoleone. Si trattava di soldati rozzi, ma molto astuti. Sapevano come scivolare sotto le pance dei cavalli e come sbucare fuori senza farsi vedere dal cavaliere, per disarcionarlo e ucciderlo.
Ben presto, disorientati, gli squadroni arabi cominciarono a disperdersi. Quando cadde la notte, Abd-el-Kader si era ritirato, e Orano era salva.
L'anno seguente, al fianco dei Legionari italiani del 5° Battaglione, gli spagnoli combattevano ancora: in giugno prendevano Arzew, ed in luglio combattevano per la presa e, più tardi, per la difesa di Mostaganem.
Il 9 aprile 1833 un nuovo Colonnello veniva destinato al comando della Legione Straniera. Si chiamava Bernelle, ed avrebbe presto inciso il nome di un'altra vittoria sulla lapide del suo reparto, con la presa di Kolea, a sud-ovest di Algeri. Ma il nome di Bernelle è soprattutto legato alla più cruenta prova del fuoco che la Legione di allora avesse mai affrontato, e che quasi la distrusse: la guerra Carlista (1835-38).

I guai cominciarono nel 1833, quando il morente re Ferdinando VII cedette il trono a sua figlia Isabella, che allora aveva tre anni ed era ancora sotto il controllo della madre, la regina Maria Cristina. Il fratello del re, Don Carlos, contestò il diritto alla successione della bambina, e organizzò una cruenta rivolta nel nord del paese.
Con un accordo trilaterale, Portogallo, Gran Bretagna e Francia decidevano, nel giugno 1834, di intervenire in difesa dell'Infanta di Spagna.
Le prime truppe a raggiungere la Spagna furono 12.000 inglesi che si accamparono intorno a San Sebastiano. Il corpo di spedizione francese arrivò poco dopo. Era costituito, ancora una volta, dalla Legione Straniera, assoldata dalla regina Maria Cristina, con la promessa che le truppe sarebbero state assistite e foraggiate dalla Spagna.Ma all'ultimo momento, due di questi Battaglioni furono inviati d'urgenza in aiuto di una colonna francese ataccata da Abd-el-Kader nei pressi di Orano.
Ancora una volta i Legionari "fecero miracoli", sacrificandosi in retroguardia per dare tempo al Gen.Trezel ed ai suoi battaglioni di sfuggire ad un potenziale massacro alle saline di Macta, dal 27 al 29 giugno 1835. Riunitasi, la Legione sbarcava il 19 agosto 1835 a Tarragona.
Le guerre civili sono raramente scontri cavallereschi; la contesa fra i "Carlisti" ed i sostenitori della regina, i "Cristinos", non fece eccezione, come imparò la Legione negli ultimi mesi del 1835 e nell'inverno che ne seguì. A metà settembre, un avamposto difeso da 30 Legionari al comando del S.Ten. Dumoustier, veniva catturato dai "Carlisti". Ai Legionari venne proposto di passare "dall'altra parte della barricata". Rifiutarono tutti. Per parecchi giorni, dopo la cattura, essi vennero trascinati di villaggio in villaggio, legati, nudi e con gli occhi strappati. Per sua fortuna, ogni tanto, qualcuno veniva ucciso.
E' difficilmente condannabile, alla luce di questi avvenimenti, il Cap. Ferrary, il quale catturata un'unità carlista, a sua volta decise di non fare prigionieri.
Prima del 1836, la Legione era stata essenzialmente una unità di fanteria. Bernelle-promosso Maresciallo d'Armata- decise di trasformarla in una unità autonoma con le relative forze di supporto e ricognizione.
Decise per la formazione di una unità di artiglieria sotto il comando del Cap. Rousselet, di una unità del genio ("zappatori"), e di alcuni squadroni di cavalleria, perlopiù composti da lanceri polacchi. Altra innovazione assai importante, fu il "reimpasto" delle nazionalità all'interno dei reparti, che lo stesso Bernelle volle in tutti i Battaglioni della Legione. I contrasi nazionalistici, che le reclute si portavano dietro in Legione, e che qualche volta avevano generato tensioni tra i Battaglioni nazionali, diventavano così ricordi del passato: con le nazionalità fuse e mischiate sin nelle più piccole unità, essi non avevano più possibilità di esistere. Un altro ovvio vantaggio portato da questa innovazione, fu il coordinamento e la unità di ideali di un reparto, i cui effettivi, da quel momento, avrebbero dovuto parlare il francese.
Il 1836 fu un anno difficile per la Legione Straniera, segnato da due vittoriosi ma costosi combattimenti: l'azione a Tirapegui, il 24 aprile, e la battaglia di Zubiri, dove i "carlisti" avevano attaccato una linea di difesa tenuta dall'esercito della regina, furono i cannoni di Rousselet a salvare la situazione. I "carlisti" si ritirarono, ma non prima che il 3° e 4° Btg. della Legione avessero perso 300 uomini.
Tutto ciò che Bernelle chiese alla fine degli scontri, per alleviare le sofferenze dei suoi Legionari, fu che le autorità spagnole rispettassero la loro promessa di rifornirli di cibo e di vestiario, nonchè di pagarli. Al rifiuto delle autorità spagnole, Bernelle si infuriò, e venne esonerato dal comando.
Il suo sucessore, Col. Conrad, non ottenne maggior successo. Ancora per due lunghi anni la Legione, senza un soldo, demoralizzata ed affamata, si trascinò da una battaglia all'altra lungo tutta la catena montuosa dei Pirenei. I Legionari presero parte ad un centinaio di scontri, ed il 2 giugno 1837 giunsero a Barbastro.Qui il Col. Conrad rimase ucciso, e sempre qui cominciò l'agonia della "Vecchia Legione", dopo una sanguinosissima battaglia che ne ridusse gli effettivi a quelli di un semplice battaglione. I superstiti furono raccolti a Pamplona, dove attesero altri sei mesi senza paga e senza razioni, prima che le loro sofferenze terminassero.
Dei circa 5.000 uomini che erano sbarcati in Spagna nel 1835,poco meno di 500 rientrarono in Francia. Il martirio spagnolo era finito.

La Legione stessa non si credeva tanto robusta da riuscire a sopravvivere ad un "salasso" del genere: ma sopravvisse. Mentre Bernelle e Conrad stavano combattendo in Spagna, altri stranieri si erano arruolati nel sud della Francia, per formare un secondo reparto da inviare in Algeria. Questa "Nuova Legione", forte di due Battaglioni, sbarcava in Africa nei primi giorni del 1837, in tempo per prendere parte alla seconda campagna organizzata dai francesi contro la città fortezza di Costantina.
L'anno precedente, aveva avuto luogo un primo tentativo di espugnare questa cittadella, fortemente difesa dall'artiglieria, e sita su di un altopiano roccioso, circondato da profondi canaloni. Il secondo attacco a Costantina cominciò il 9 ottobre 1837, e durò quattro giorni. Il 13, in testa alle formazioni più avanzate, la Legione si apriva la strada combattendo, attraverso una breccia nelle mura. Per tutto il giorno i Legionari combatterono nelle strade e nei vicoli della vecchia città araba, incontrando ovunque un'accanita resistenza.
Finalmente, mentre la notte cominciava a calare, il Sgt.Mag. della Legione Doze catturava l'ultima bandiera nemica, che è ancora esposta al museo "Les Invalides" di Parigi.
Dall'inizio del 1838 la Legione aveva raggiunto i tre Battaglioni di organico. Questi Legionari entrarono in azione in numerosi scontri, particolarmente vicino ad Algeri, contro le forze di Abd-el-Kader, l'irriducibile nemico
Come sempre poi, la Legione si dedicò per molto tempo anche ai lavori di costruzione. Fra Douera e Boufarik fu costruita una strada ferrata che rimase famosa per molti anni come " Chausseè de la Legion" (ferrovia della Legione).

Nel 1841, essendo aumentato notevolmente il numero dei Battaglioni in forza alla Legione, essi furono inquadrati in due reggimenti separati. Il 1° Regiment Etranger(1°R.E.) veniva distaccato ad Algeri, con una zona di operazioni corrispondente all'area occidentale dell'Algeria. Fu proprio il 1° R.E. a fondare la città che sarebbe diventata la "casa madre" della Legione, Sidi-bel-Abbès, a cira 80 Km. a sud di Orano.
Il reggimento organizzò un'estenuante routine di pattugliamenti in quella zona del paese, effettuati da "colonne volanti" che si spostavano nel deserto a piedi, combattendo, costruendo, stabilendo avamposti, tracciando e ritracciando piste e scontrandosi molto spesso con reparti di guerrieri arabi istigati dall'irriducibile Abd-el-Kader.
Il 2° Regiment Etranger (2°R.E.) fu invece distaccato a Bona. Da qui, esso diresse tutta la sua attenzione a ovest, verso gli altipiani della Kabylia ed a sud, oltre Biskra, dove le sabbie del Sahara lambiscono i piedi dei monti Aures.
Proprio fra questi monti il Reggimento si distinse, il 15 marzo 1844, nel durissimo scontro per uno degli ultimi capisaldi della resistenza in quella zona, il viillaggio berbero di M'Chounech. Questo combattimento fu compiuto dallo stesso figlio di Luigi Filippo, il Duca d'Aumale. A M'Chounech il 2°R.E. guadagnava la sua Bandiera di Guerra. Ma la zona non fu pacificata ancora per molto tempo. Gli uomini delle tribù Chouia erano nemici testardi, ed i confini del Sahara venivano spesso disturbati dalle loro scorribande.
Oltre che sconfiggere definitivamente questi nemici sulle colline, al Col. Corbuccia, comandante del 2°R.E., venne ordinato nel luglio 1849 di attaccare un nido di insorti presso l'oasi di Zaatcha. Inadeguatamente informato, il Colonnello veniva messo in crisi dalla forza della difesa araba; fu costretto a ritirarsi, dopo aver perso 32 uomini e con 115 feriti. Un secondo assalto venne subito organizzato, con forze assai più ingenti: 4.000 uomini, appoggiati dall'artiglieria del Gen. Herbillon.
L'oasi di Zaatcha era costituita da un enorme palmeto, circondato da un fossato profondo circa sei metri; le poche vie d'accesso erano difese da solide costruzioni, edificate da esperti e risoluti guerrieri. L'attacco venne scagliato in un rigido clima invernale e le truppe, inoltre, erano tartassate dal colera, giunto nell'accampamento con i rifornimenti provenienti dalla Francia. Dopo sei settimane di feroci combattimenti i Legionari presero finalmente l'oasi, con un ultimo assalto alla baionetta, il 26 novembre 1849. La colonna di Herbillon aveva perso, tra morti e feriti, 1.500 uomini.
Sebbene, più o meno tutta l'Algeria fosse già stata pacificata, rimanevano ancora alcune zone pericolose. Questo valeva in particolare per la Kabylia. Per i francesi, la Kabylia rappresentava una seria minaccia al loro dominio in Algeria. Nell'autunno 1856, fu organizzata una grande offensiva e molte colonne francesi conversero lentamente nel cuore roccioso della Kabylia.
Il 24 giugno 1857, la Legione aggiunse il nome di Ischeriden a quelli delle sue più grandi battaglie.

4.000-5.000 cavalieri arabi tenevano la cresta di un'altura scoscesa. Il primo assalto francese fallì, nonostante l'appoggio dell'artiglieria.Il Gen. Mac Mahon, comandante della colonna, ordinò al 2°R.E. di entrare in azione. I Legionari avanzarono salendo il pendio schierati come in parata, in impeccabile ordine e con le armi a spalla; non spararono un solo colpo.
Questa straordinaria manifestazione di sicurezza sconcertò gli arabi, e quando i Legionari giunsero alla cresta attraversando il fuoco nemico e misero in atto l'ultimo assalto alla biaonetta, gli uomini delle tribù abbandonarono in fretta le posizioni, e si dispersero.
Con la battaglia di Ischeriden, la pacificazione dell'Algeria poteva dirsi completata. I Legionari potevano rientrare a casa, a Sidi-bel-Abbes.

Nel 1853, lo Zar Nicola I° decise di occupare Costantinopoli; egli mirava ad assicurare alla Russia il controllo del Bosforo e il libero accesso al Mediterraneo, nonchè a dare il "colpo di grazia" all'Impero Ottomano.
Immediatamente, la Turchia si appellava alla Francia ed alla Gran Bretagna per ottenerne l'aiuto. Il 14 settembre 1854, gli alleati sbarcavano in Crimea senza incontrare resistenza. Dopo una prima vittoria sui russi ad Alma, francesi e inglesi si fermarono per organizzare l'assedio di Sebastopoli.
Era in questa città-fortezza,formidabilmente difesa, che si erano concentrati l'Esercito e la flotta russa, per attaccare Costantinopoli. L'assedio sarebbe durato un intero anno. Le sofferenze provocate dal clima, venivano aggravate da quelle di un'epidemia di colera che colpì, tra le migliaia di uomini, anche i due Comandanti delle forze alleate: Raglan e Saint-Arnaud.
Rappresentata sul teatro delle operazioni dal 1° R.E., la Legione raggiungeva in Crimea l'organico di una Brigata, con l'arrivo di rincalzi dal 2° R.E..
Il 1° maggio 1855, dopo che le truppe avevano passato un rigido inverno in trincea, il comando alleato decideva di lanciare un'offensiva che avrebbe dovuto sbloccare la situazione sul fronte. Essa fallì, con un costo di vite umane altissimo.
Fra i 118 morti ed i 480 feriti della Legione, vi era anche il Col. Vienot del 1° R.E. Il suo nome sarebbe però sopravvissuto: la Legione gli avrebbe intitolato la sua caserma di Sidi-bel-Abbes prima, quella di Aubagne più tardi.
Il 18 giugno, un altro attacco veniva lanciato, questa volta contro la chiave del sistema difensivo russo: la ridotta Malakoff. Una volta ancora gli assalitori vennero respinti: 6.000 soldati inglesi e francesi furono sacrificati in un'operazione assai confusa. L'8 settembre gli alleati ci riprovavano.
Questa volta la Legione era rappresentata da un pugno di uomini, ma questo centinaio di Legionari costituì la punta di diamante dell'attacco, sempre davanti a tutti, correndo sotto il fuoco nemico e trasportando scale e travi di legno. Nel breve lasso di tempo in cui le altre truppe raggiungevano i propri obiettivi, i Legionari del Sergente Valiez avevano già costruito "rampe" e impalcature di fortuna a ridosso delle difese russe. Quella sera, finalmente, la ridotta Malakoff cadeva, e la notte stessa i russi iniziarono l'evacuazione di Sebastopoli.
La guerra di Crimea ebbe termine nell'agosto 1856. La ricompensa per l'opera svolta dalla Legione fu lo sbandamento più completo. Gli uomini superstiti furono imbarcati e ricondotti a Sidi-bel-Abbes, dove vennero rialluolati in una delle due "Nuove Legioni Straniere"
La nuova "2° Legione Straniera" interamente composta da svizzeri, veniva ridesignata "1° Reggimento Stranieri". Automaticamente, i reduci della Kabylia e della Crimea venivano a trovarsi subordinati agli svizzeri,all'interno della Legione, prendendo il nome di "2° Reggimento Stranieri".
Questo 2° R.E. portava più o meno la divisa della fanteria francese: pantaloni cremisi e giacca blu; mentre gli svizzeri del 1° R.E. si distinguevano per un giaccone verde: il rosso ed il verde sarebbero diventati, da questo momento, i colori della Legione.

L'intervento francese in Italia nasceva come una più che logica conseguenza della politica "liberale" di Napoleone III°. Egli, infatti, aveva sempre nutrito grande simpatia per i "carbonari" italiani che avevano combattuto nell'ombra per tanto tempo, inseguendo il sogno di un'Italia unita ed indipendente
L'Italia a quei tempi era in gran parte occupata dall'Austria. La campagna cominciò nella primavera del 1859, e la Legione vi fu presente.
Il 4 giugno i reparti francesi giungevano in vista della città di Magenta e degli austriaci. Alle tre del pomeriggio, i Legionari si trovavano in una vasta zona fittamente coltivata, rotta solo da alcune siepi, e da vigneti.
Letale per l'impiego della cavalleria, questo terreno era l'ideale per la fanteria. Fermandosi solo per sparare, gli austriaci avanzavano tra i boschetti e lungo i sentieri. Sul fianco sinistro dello schieramento francese, i Cacciatori a Cavallo cominciarono a indietreggiare. Ritto in piedi sulle staffe il Col. de Chabrière della Legione, tuonava:"via gli zaini! Avanti Legione!". Baionetta inastata i Legionari si lanciarono all'attacco, e questo momento di particolare impeto dei francesi, disorientò gli austriaci.
Essi infatti, dapprima resistettero stringendo le fila e poi, poco a poco furono costretti alla ritirata. Prima di sera la vittoria arrideva ai francesi.
Il giorno successivo, Milano veniva liberata; la Legione marciò attraverso la città in testa alle truppe francesi; si era guadagnata questo onore con il sangue versato.
Erano stati uccisi o feriti ben 15 dei suoi Ufficiali fra cui il Col. de Chabrière, e circa 300 Legionari.
Tre settimane dopo, la cruenta battaglia di Solferino, concludeva la campagna. Dopo una deviazione che l'avrebbe portata a Parigi per la sua prima, trionfale parata attraverso la Capitale, la Legione rientrava in Algeria per restarvi, come sempre, ben poco.

Tre anni dopo la campagna italiana si prospettava una nuova avventura e laggiù, in Messico la Legione sarebbe definitivamente entrata nella leggenda.
Il Messico era a quei tempi un paese particolarmente difficile, ed i partigiani di Juarez erano soliti non concedere al nemico un attimo di tregua. La Legione si sarebbe accorta di ciò assai rapidamente; il 1° aprile, dopo un viaggio in treno di una giornata attraverso la regione di Tejera, i Legionari marciarono verso la cittadina di Chiquihuite, dove il Col. Jenningros stabilì il Comando di Reggimento.
Durante la marcia di avvicinamento, erano stati lasciati indietro, a sorveglianza e protezione dei campi di lavoro lungo la ferrovia,piccoli distaccamenti di Legionari.
Il 18 aprile uno dei campi di lavoro veniva attaccato e saccheggiato dai partigiani di Armando Diaz, sindaco di Jalapa.Gli operai messicani del campo venivano condotti via e la loro scorta di Legionari, dopo aver opposto un'accanita resistenza, venne massacrata al completo.
Due giorni dopo, Diaz si lanciava in una seconda impresa, ma questa volta il suo obiettivo era un'intera compagnia della Legione. Sin dal principio degli scontri i Legionari contrattaccarono violentemente disperdendo rapidamente gli assalitori.
Il Ten. Milson, un prussiano,uccideva in un combattimento corpo a corpo lo stesso Diaz: da questo momento i "juaristi" capirono che con la Legione c'era poco da scherzare, e impararono a temerla.
Il 29 aprile, esattamente un mese dopo lo sbarco in Messico, il Col. Jenningros annunciò che un'imponente carovana francese stava lasciando Vera Cruz diretta a Puebla.
A parte 3 milioni di franchi in oro, viveri e munizioni, la carovana trasportava equipaggiamenti ed armamenti essenziali, per poter risolvere la situazione di Puebla, il cui assedio si trascinava da quasi un anno.
Il Col. Jenningros dispose l'invio di una compagnia di Legionari ad incontrare la carovana.
La 3^ Cmp. del 1° R.E. era disponibile, seppur limitata nell'organico dalle malattie, con 62 tra uomini di truppa e Sottufficiali. Essa però, a causa del colera e della febbre gialla, non aveva più Ufficiali.
Così il Capitano DANJOU, uno degli Ufficiali dello Stato Maggiore di Jenningros, si offerse di assumerne il comando. Altri due Ufficiali, i Sottotenenti MAUDET e VILAIN, venivano assegnati alla 3^ Cmp. in aiuto di DANJOU: si trattava di due giovani Ufficiali che pur avendo ricoperto fino a quel momento incarichi di tipo logistico-organizzativo, erano in possesso di una certa esperienza di combattimento.

Allo scoppio della Guerra Franco-Prussiana, molti stranieri naturalizzati in Francia si arruolarono a combattere per la loro patria adottiva. Questi volontari furono raccolti nel 5° Battaglione Stranieri, nominalmente parte della Legione.
Essi furono praticamente annientati prima di Orleans, il 10 ottobre 1870.
Il Comandante Araga e cinque altri Ufficiali furono uccisi, ma è interessante notare che tra i sopravvissuti si trovava un certo S.Ten. Kara, in realtà il Principe Karageorgevich, futuro Re Pietro I° di Serbia.
Ciò che rimase del 5°Btg fu presto affiancato da due Battaglioni formati dalla Legione in Algeria. I Legionari combatterono durante un inverno particolarmente rigido ed il 13 gennaio 1871 riconquistarono Montbeliard. Ma la Patria era ormai persa, e l'armistizio che la Francia fu costretta a firmare il 28 gennaio, trovò la Legione presso Besançon. Il 17 marzo raggiunse Versailles, avendo perso 14 Ufficiali e 916 uomini.
Nel giugno 1871 i sopravvissuti di questa sfortunata campagna rientrarono in Algeria. Alla stazione di Sidi-bel-Abbes furono ricevuti dalla Banda della Legione. I Legionari tedeschi rimasti in Africa avevano salvaguardato fedelmente le tradizioni della Legione Straniera.
Con l'Alsazia e la Lorena irrimediabilmente perdute, e senza speranza di riconquista a breve termine, il Governo della Terza Repubblica spostò il suo interesse verso i vasti territori inesplorati d'Asia e d'Africa, dove sperava di stabilire colonie.
La XIX Armata, "l'Armata d'Africa", sembrò la più indicata per questa missione. Si era arricchita di grosse esperienze in battaglia, guadagnate in decine d'anni di servizio attivo in territori difficili, in mezzo a popolazioni povere e preda delle malattie.
Per quelle campagne dove la Francia sarebbe stata impegnata a costruire strade, aprire mercati, creare porti e insediamenti, era naturale che la Legione Straniera figurasse tra le Unità più adatte.

Nel 1883, la Legione venne mandata nel Tonkino (oggi Vietnam), allora provincia del nord dell'Impero di Annam, con capitale Huè. Il Tonkino era a quel tempo dichiarato Protettorato francese dall'Imperatore stesso, ma in pratica era terra preda delle scorrerie di numerose bande di pirati (conosciute come "Bandiere Nere") supportate da truppe cinesi regolari inviate dall'Imperatrice cinese, dichiaratamente ostile.
L'8 novembre 1883, il 1° Battaglione della Legione sbarcò ad Haiphong. Era quello il primo atto di una saga che sarebbe durata ben settanta anni.
Il Comandante della prima spedizione, l'Ammiraglio Courbert, decise che avrebbe ripulito il Tonkino. Il primo passo sarebbe stato quello di attaccare le roccaforti delle "Bandiere Nere" Son Tay e Bac Ninh.
I Legionari del 1° Battaglione si distinsero per la cattura di Son Tay, difesa da qualcosa come 25.000 soldati nemici. L'anno seguente, supportata da un secondo battaglione comandato da Hutin, la Legione attaccò la cittadella di Bac Ninh.
La sua condotta sotto il fuoco portò il Gen. De Negrier, comandante delle operazioni, a dichiarare che "l'onore di essere prima ad entrare a Bac Ninh spetta alla Legione". Ma sarebbe stato presso un altro vecchio forte cinese, Tuyen Quang, che la Legione avrebbe mostrato il suo vero valore.
Sotto il comando del coraggioso Comandante Dominè la 1^ e 2^ Cmp. del 1° Reggimento formarono la spina dorsale della guarnigione, composta da 600 uomini, che difese Tuyen Quang dal 23 gennaio fino al 3 marzo 1885. Per quasi sei settimane il forte fu tagliato fuori e sotto continuo attacco di un'Armata cinese composta da 20.000 uomini coraggiosi, ben armati e profondi conoscitori delle tecniche di minamento e assedio.
In un primo tempo i cinesi circondarono Tuyen Quang con una cintura di tricee, ancorate ad un certo numero di villaggi fortificati. Da queste linee mossero tutti i loro assalti. Il 26 gennaio bombardarono il Forte, appiccarono incendi e subito mandarono tre colonne di fanteria all'assalto con l'obiettivo di catturare una torretta avanzata, piuttosto esposta e difesa dal Sgt. Lebel e dai suoi uomini. I cinesi furono respinti da tutti i lati, ma il 30 gennaio la torretta, troppo isolata per essere difesa oltre, venne abbandonata. Gli eventi da allora si susseguirono rapidamente. La Guarnigione francese non aveva in quel momento la minima speranza di aiuto esterno e doveva basarsi sulle sue forze. I cinesi, dal canto loro, continuavano a bombardare frequentemente e a costruire trincee verso il forte, fintanto che alcune sezioni dei muri di cinta crollarono. Le brecce createsi vennero riparate dai genieri del Sgt. Bobillot, o da altri Legionari, usando improvissate palizzate di legno.
Il 10 febbraio, i cinesi avevano raggiunto con le trincee l'angolo sud-est delle mura, e il giorno seguente lo fecero saltare. Temendo nuove brecce nelle mura, il Comandante Dominè ordinò che si costruisse una seconda linea di difesa, a circa settanta metri all'interno delle vecchie mura. Con lo spettro di perdere altro terreno, la guarnigione perserverò nel contestare il perimetro del forte ai cinesi.
Il 17 febbraio il Cap. Dia, comandante le truppe della guarnigione, fu ucciso. Il giorno seguente fu la volta del Sgt. Bobillot. Quattro giorni più tardi, una grossa porzione delle mura esterne venne fatta saltare e il nemico si roversò all'interno. La Legione contrattaccò, nonostante l'esplosione di una mina che uccise 12 Legionari. L'attacco fu comunque respinto.
Il 24 febbraio quasi tutta la forza disponibile cinese si impegnò in un attacco disperato in una notte senza luna. I Capitani Cattelin e Borelli trascinarono i Legionari al contrattacco e l'alba vide i cinesi in ritirata, ancora una volta.
Il 25 febbraio un'altra mina saltò, il 28, una carica di oltre 200 libbre di polveri distrusse l'ultimo pezzo di muro ancora intatto: cinesi e francesi combatterono ferocemente tra le rovine fumanti, per quattro ore. Ma quello era l'ultimo sforzo disperato degli attaccanti: la colonna dei rinforzi al comando del Gen. Giovaninelli era vicina. Il 3 marzo i sopravvissuti, di fronte alla loro semidistrutta cittadella, presentarono le armi ai loro salvatori (questo gesto sarebbe divenuto tradizionale in tutta l'Indocina).
Le due Compagnie della Legione avevano perso un terzo della loro forza: 32 morti e 126 feriti.
Questa sarebbe stata una delle ultime azioni ingaggiate fra francesi e cinesi; il 1° aprile, infatti, un trattato portò alla fine della campagna. Negli anni che seguirono, la forza francese si impegnò a rappacificare un paese da sempre vessato da briganti di ogni tipo e frammentato in molte tribù. Nuovamente, dunque, la Legione giocò un importante ruolo di paziente ricostruzione e riorganizzazione che gradualmente portò alla rinascita di una società pacifica.
Nel 1930, le varie unità della Legione che servivano in Indocina furono amalgamate sotto il titolo di 5° Reggimento Straniero di Fanteria (5° R.E.I.) detto anche "Reggimento del Tonkino".

Nel 1892, Ouidah, era un piccolo porto sulla costa del Dahomey, era uno degli approdi commerciali francesi. Fino a quella data, quegli approdi erano sotto la protezione di un trattato di pace con il Re locale, Behanzin. Da alcuni anni prima, agenti tedeschi avevano fatto credere al Re Behanzin che dal 1870 la Francia non esisteva più. Il re aveva quindi preso a molestare quelle installazioni francesi e addirittura minacciato di annientarle. Quei propositi erano poi supportati dal fatto che il re stava assemblando un esercito considerevole, e soprattutto dotato di armi moderne. L'acquisto di fucili Mauser fu accompagnato dall'arrivo di istruttori tedeschi.
Quando le minacce sembravano doversi tramutare in realtà, la Francia decise di intervenire. Una spedizione di 4.000 uomini fu mandata a sud, sotto il comando del Col. Dodds; essa includeva un Battaglione di 800 Legionari, comandati dal Magg. Faurax. La missione: assediare la città di Abomey, la capitale del Dahomey, e costringere al negoziato Behanzin. Lo sbarco ebbe luogo senza incidenti il 26 agosto1892. Pochi giorni più tardi i Legionari di Faurax intrapresero la marcia. Avrebbero dovuto congiungersi ad un distaccamento precedentemente mandato avanti per pacificare il Decamè, una zona lungo il fiume Ouèmè.
Durante i primi dieci giorni tutto andò bene. La marcia non era certo delle più rapide: la bussola era l'unico strumento che li potesse guidare, e la strada doveva essere aperta nella boscaglia a colpi di machete. Finalmente l'11 di settembre, Faraux si congiunse con la prima colonna sul fiume Ouèmè. Da li i due reparti proseguirono insieme la marcia fino alla notte del 18 settembre, quando bivaccarono presso Dogba, in un accampamento lungo il fiume. Spalleggiati dall'argine del fiume stesso, i Legionari trincerarono l'accampamento sugli altri due lati, per maggior sicurezza.
All'alba del 19, quando la tromba stava per dare la sveglia, il sottobosco attorno al campo si animò improvvisamente di guerrieri Dahomey. Alcuni di essi si lanciarono sui francesi dall'alto degli alberi che sovrastavano i bivacchi. Da un attimo all'altro una confusione indicibile si sparse ovunque. Ma passato il primo momento di shock, la Legione reagì: il contrattacco alla baionetta fu il suo istintivo e tradizionale modo di rispondere. Alcuni dei guerrieri erano armati con fucili Mauser e carabine a ripetizione Winchester, e per quattro volte si scatenarono all'attacco; per altrettante volte furono ricacciati indietro.
Il corpo a corpo durò fino alle dieci del mattino, quando improvvisamente, così come erano comparsi, i guerrieri Dahomey sparirono nella boscaglia. Essi lasciarono 832 morti sul campo, mentre la Legione accusò 45 perdite, compreso il Magg. Faurax. Le sue ultime parole furono per il Col. Dodds:Siete rimasto soddisfatto dei miei uomini?".
Due settimane più tardi, a Porguessà, il 4 ottobre, il S.Ten. Amelot venne ucciso: il nemico era sempre ai margini della strada percorsa dai Legionari. Strisciando sui lati della colonna in marcia, esso operava attacchi fulminei ogni volta che se ne presentasse la possibilità. Nel corso di questi scontri di percorso, i Dahomey mandarono persino gruppi di donne all'attacco, le quali non chiedevano nè offrivano pietà.
Durante l'ultima settimana di ottobre il Col. Dodds fermò i suoi uomini per un meritato riposo. Essi non giunsero ad Abomey se non il 17 di novembre, quando però Behanzin era ormai fuggito, lasciando la città in fiamme.
Degli 800 Legionari partiti, ne ritornarono in Algeria soltanto 450.