Muukalaislegioona sai alkunsa Ranskan kuningas Ludvig Filipin ja marsalkka Nicolas Jean-de-Dieu Soultin 9. maaliskuuta 1831 allekirjoittamasta määräyksestä, jossa maan armeijaan määrättiin perustettavaksi uusi yksikkö, Muukalaislegioona.