Créé le 1^er janvier 1885 suite au décret du 14 décembre 1884, le 2^er régiment étranger est, à l'origine, basé à Saïda. Il a été créé sur les bases du 2^er Régiment de la Légion étrangère. Ce dernier a vu son histoire commencer en 1841. Le 2^ème R.E.I. est donc l'un des plus vieux régiments de la Légion.

En plus de la devise de la Légion, HONNEUR et FIDELITE, sont inscrites les batailles de : SEBASTOPOLE (1855), KABYLIE (1857), MAGENTA (1859), CAMERONE (1963), EXTREME-ORIENT (1885 - 1885), DAHOMEY (1892), MADAGASCAR (1898 - 1905), MAROC (1907 - 1913), (1926), INDOCHINE (1946 - 1954).

Avec les nécessité de la Grande Guerre, le Régiment de Marche de la Légion Etrangère est créé par des éléments du 1^er Régiment étranger et par tous les éléments du 2^ème R.E. Par conséquent, ce dernier est dissous en 1915. Il sera reformé en 1922 à Meknès. Guerre différente (toujours mondiale), effets identiques, le 2^ème R.E. est dissous en 1943 pour former le 3^ème R.E.I.M. puis R.M.L.E.

Avec la guerre d'Indochine qui se profile à l'horizon, le régiment est reformé en 1946 sous l'appellation de Régiment de Marche de la Légion étrangère - Extrême Orient. Il prend le nom de 2^ème R.E.I. en 1948.

La fin de l'Algérie française voit aussi la troisième dissolution du régiment le 30 janvier 1968 au départ de Mers El-Kébir.

Reformé à Corte en Corse en 1972, il s'installe à Nîmes en 1983 dans le Quartier Vallongue.

Le 2^ème R.E.I. est décoré de 3 palmes T.O.E. et de la fourragère des T.O.E.