Août 1834, le premier drapeau de la Légion étrangère arrive en Algérie dans les mains du colonel Combes, remis à Marseille par le Duc d'Orléans, fils aîné du roi. Il porte l'inscription : "Le Roi des français à la Légion étrangère".

La première devise présente sur ses drapeaux est celle des unités du régime général : "Honneur et Patrie". Apparaîtra ensuite, vers 1840, la première devise de la Légion : "Valeur et discipline".

En 1920, dans le but de recréer une cohésion forte et des liens avec le "vieille" Légion, le général Rollet veut, entre autre, instaurer des traditions "anciennes".

Cette année, le 20 novembre 1920, la devise initiale de la Légion ,"Valeur et Discipline", est remplacée par "Honneur et Fidélité", devise du régiment de Diesbach, licencié en 1792, sous l'ancien régime qui était reprise comme un symbole de la pérennité de la tradition des troupes étrangères au service de la France.