Il 1 aprile 1948 nacque in Indocina la prima unità di paracadutisti della Legione. Formata in seno al 3° R.E.I. con Legionari provenienti, oltre che da questo stesso reparto, dal 2° R.E.I.e dalla 13^ D.B.L.E.. La neocostituita compagnia venne subito inviata a combattere. Tre mesi dopo, il 1 luglio, un intero battaglione parà venne creato a Campo Khamisis in Algeria: si trattava del 1° Battaglione Paracadutisti Stranieri (1° B.E.P.), che sbarcò ad Haiphong il 12 novembre. Nel frattempo in nord Africa, si continuava a provvedere alla formazione di personale destinato a costituire un secondo battaglione, il 2° B.E.P., istituito il 2 ottobre. Il 9 febbraio anche questa unità raggiunse l'Indocina. Il 3° B.E.P., creato succesivamente in Algeria, ebbe solo il compito di formare e istruire il personale assegnato ai due reparti operativi. Nel 1951 venne costituita una compagnia aviorifornimento (C.E.R.A.), e ne l 1953 una compagnia mortai pesanti da 120 mm.(C.E.P.M.L.) che andarono a rinforzare il 1° e 2° B.E.P. Raccontare la storia dei due B.E.P. in Indocina equivale a raccontare tutta la storia di questa sfortunata campagna. In effetti questi due reparti parteciparono a tutte le grandi operazioni sino all'olocausto di Dien Bien Phu dove entrambi si coprirono di gloria. Il 1° B.E.P. venne annientato due volte durante la guerra d'Indocina: la prima, nell'ottobre 1950, sulla Strada Coloniale n° 4 (R.C.4) sul massiccio di Coc Xa dove si sacrificò per venire in aiuto alla "colonna Charton"; la seconda volta nel 1954 durante la battaglia di Dien Bien Phu dove intervenne innumerevoli volte a sostegno dei punti d'appoggio, lanciando furiosi contrattacchi contro le ondate vietminh.
Quanto al 2° B.E.P., esso fu il Battaglione delle "missioni impossibili". Questa unità d'elite partecipò, tra l'altro,al salvataggio della guarnigione di Nghia-Lo assediata da due Divisioni vietnamite (ottobre 1951); ai combattimenti della R.C.6, la strada di Hoa Binh (novembre 1951); ai violenti contrattacchi intorno a Nasan (ottobre 1952); al raid su Langson, che permise di distruggere il più importante deposito di armi e munizioni del gen. Giap (luglio 1953). L'11 aprile 1954 , il 2° B.E.P. venne aviolanciato su Dien Bien Phu dove conobbe la stessa sorte dell'unita gemella. Il 1 dicembre 1955 il 2° B.E.P., che aveva incorporato il personale del 3° B.E.P., divenne il 2° Reggimento Paracadutisti Stranieri (2° R.E.P.). Dislocato in Algeria, dove venne raggiunto dal 1° R.E.P. costituito il 1 settembre, il 2° R.E.P. fu impiegato principalmente nel Costantinese, negli Aures, nelle Nementchas e nella regione di Guelma. Nel frattempo il 1° R.E.P. prese parte alla spedizione su Suez e prima di tornare a combattere nel deserto, venne inviato ad Algeri, dove riuscì a stroncare e a smantellare le infrastrutture del FLN. Sino al 1960 i due R.E.P. furono i principali artefici del successo del piano "Challe". Nel 1961 si combatteva ancora, anche se il destino dell'Algeria era già segnato. Il 22 aprile, il giorno del "putsch dei generali", il 1° R.E.P. fece la sua scelta: il disperato tentativo di opporsi all'abbandono dell'Algeria gli fu fatale. Il 30 aprile, giorno di Camerone,il Reggimento, uno dei più gloriosi dell'esercito francese, venne sciolto. Dopo il cessate il fuoco il 2° R.E.P. venne raggruppato a Bou Sfer, nell'enclave di Mers-el Kebir. Nel giugno 1967 il Reggimento lasciò la Tunisia per la Corsica, dove un primo distaccamento si era trasferito nel 1963. Il 2° R.E.P. si installò al campo del Fiume Secco, che diverrà poco dopo "Camp Raffalli" in memoria dello "Chef d'esquadron" Raffalli comandante del 2° B.E.P. in Indocina, morto il 1 settembre 1952 sulle rive del fiume Giong. Il 2° R.E.P. fu inviato in Ciad nel 1969-70, nel 1978, nel 1983-84 e nel 1986. Nel 1976 la 2^ Compagnia, presente momentaneamente a Gibuti, partecipò alla liberazione di una trentina di bambini presi in ostaggio da un gruppo di terroristi.Un'altra azione, giudicata unanimamente esemplare, fu quella compiuta dal Reggimento il 18 maggio 1978, quando il reparto venne lanciato alla periferia di Kolwezi (Zaire) per far cessare il massacro della popolazione europea da parte dei ribelli "Katanghesi". Nel 1982 tre Compagnie del 2° R.E.P. vennero inviate in Libano per proteggere l'evaquazione dei Feddayin palestinesi. Infine, il 2° R.E.P. venne impiegato nella "guerra del Golfo" del 1990, e in Bosnia nel 1993-94.
