Deuxième légion
Le , Louis-Philippe, roi de France cède à la reine d’Espagne Isabelle la Légion étrangère.
4 100 hommes, étrangers au service de la France et officiers français passent alors dans les rangs de l'armée espagnole, en butte avec les troupes carlistes.
Mais la campagne d'Algérie nécessite de nombreuses troupes et dès le , le roi signe une ordonnance qui porte création d'une nouvelle légion.
La création de la deuxième Légion
Son format est tout d'abord limité à un seul bataillon. Les autres ne seront constitués que successivement, et seulement si les besoins se font sentir. Toutes les dispositions de l’ordonnance du (date de création de la Légion) sont remises en vigueur.
Le premier bataillon est immédiatement formé à Pau. Le , le chef de bataillon Bedeau en prend le commandement. Un mois plus tard, l’état-major du bataillon et les deux premières compagnies sont formés. Six autres compagnies voient le jour en juin 1836.
Nouvelle dissolution
Mais au mois d’août, suivant, le bataillon est licencié et le gouvernement propose aux officiers, sous-officiers et légionnaires qui le composent d’aller servir en Espagne dans les rangs de la Division française auxiliaire, appellation de l’ex-Légion, qui combat là-bas depuis un an. Ceux qui refusent sont renvoyés dans leurs foyers. Ceux qui sont volontaires pour servir en Espagne forment un nouveau bataillon qui est dirigé sur Pampelune sous les ordres du lieutenant-colonel Conrad.
Re-création et départ pour l'Algérie
Malgré le licenciement de la Légion étrangère, les étrangers continuent à être engagés au sein de l'armée française. Les nouvelles compagnies de dépôt sont créées et en octobre 1836, un total de six compagnies est formé, rapidement suivi de deux autres en novembre
Ce nouveau bataillon est placé sous le commandement du chef de bataillon Marie-Alphonse Bedeau. Le , il quitte Pau pour s’embarquer sur le Suffren, à Toulon, en partance pour l'Algérie.
Il intègre sur place la 2e Brigade de l’armée d’Afrique, commandée par le général Négrier.
Le deuxième bataillon est formé en juillet 1837. La création des trois autres s’échelonne jusqu’en 1840. Après la prise de Constantine, en octobre 1837, au cours de laquelle le bataillon de la Légion s’est illustré, le chef de bataillon Bedeau est promu lieutenant-colonel et la formation de compagnies d’élite est autorisée. En récompense de ses faits d’armes, la Légion reçoit, le , le drapeau qui avait été remis, en 1832, à la première Légion.
Ayant atteint son effectif réglementaire, la seconde Légion étrangère est dédoublée en deux régiments étrangers.