Muukalaislegioonan salaperäinen maine johtuu muun muassa siitä, että siihen voi halutessaan pestautua salanimellä ja -kansallisuudella, mikä on aiemmin houkutellut oikeutta pakoilevia rikollisia ja seikkailijoita. Nykyisin pseudonymiteetti on symbolinen ”uuden lehden kääntäminen elämässä”, sillä taustat tarkastetaan. Kolmen vuoden jälkeen tilalle voidaan ottaa oma henkilöllisyys.