הלגיון נשלח לתגבר את כוחות צרפת באלג'יריה אשר נלחמו בכוחות מורדים ערבים אשר הונהגו על ידי עבד אל-קאדר אל-ג'זאירי אמיר ערבי אשר נחשב לאיש קדוש בעיניי המוסלמים באלג'יריה. בתחילה, זכה עבד אל-קאדר בהצלחות רבות, בזכות טקטיקות של פגע וברח ופשיטות על יישובים מבודדים, בהן נקט. כ-3,000 לגיונרים נשלחו בשנת 1837, כדי לסייע בחיסול המרד, וכן מונה מפקד חדש לאלג'יריה, תומאס בוגואד. המפקד החדש החליט לשנות את טקטיקת הלחימה, ובמקום לנוע בשירות גדולות עם ציוד כבד הוא החליט לצייד את הלגיונרים בציוד הבסיסי ביותר ולדרוש מהם לחיות מן הסביבה. שינוי זה הפך את הלגיון לכוח פעולה מהיר אשר יכל לעבור מרחקים ארוכים במהירות ולא היה זקוק לסיוע לוגיסטי מסורבל. הלגיון השתמש באותן טקטיקות בהן השתמש עבד אל-קאדר. ב-1840 החלה הטקטיקה החדשה להראות תוצאות, והמרד החל להתפורר. ב-1847 נכנע סופית עבד אל-קאדר, והוגלה לסוריה. המערכה באלג'יריה קבעה את אופיו של לגיון הזרים, כיחידה הנעה עם ציוד מינימלי, ומכלכלת את עצמה מן השטח.
לאחר הניצחון על כוחות המורדים ביצעו כוחות הלגיון עבודות תשתית אזרחיות (כגון סלילת כבישים) לשיפור פני אלג'יריה והכנתה להתיישבות צרפתית. בסיס הלגיון נקבע בעיירה הקטנה סידי בל-עבאס. עם הקמת מפקדת הלגיון בעיירה, גדלה אוכלוסייתה מכ-400 איש לכ-150,000, ובכך היא הפכה לאחת הערים הגדולות באלג'יריה.
מקסיקו.
ב-1862 נחתו כוחות צרפתים במקסיקו כיוון שנשיא מקסיקו הקפיא את תשלומי החובות של ארצו לצרפת, בריטניה, ספרד וארצות הברית. נפוליון השלישי קיסר צרפת תכנן לכבוש את מקסיקו ולהפוך את מקסיקו למדינת חסות צרפתית. הלגיון לא נשלח להשתתף בפלישה ונשאר בתפקידי שיטור ובנייה באלג'יריה. קציני הלגיון, אשר כעסו על כך שהם נשארו לבצע תפקידי שיטור ובנייה ולא נשלחו למקסיקו להשתתף במערכה, כתבו מכתב תלונה לקיסר בו הם ביקשו שהלגיון יישלח למקסיקו. ב-19 בינואר 1863 נפוליון השלישי אישר את בקשתם וציווה לשלוח כוח בגודל של חטיבה מן הלגיון להשתתף במערכה במקסיקו. ב-28 במרץ הכוח שהורכב מ-48 קצינים וכ-2,000 לגיונרים הגיע לורה קרוז במקסיקו. על הלגיון הוטלה המטלה של אבטחת צירי האספקה אשר עברו בשטחי ביצות מוכי מחלות. הפיקוד הצבאי אשר חשש מפגיעה במורל של כוחות הצבא הסדירים אם הם יוצבו באזורים מוכי מחלות, העדיף להציב בהם את כוחות הלגיון אשר היו מורכבים מזרים שכירים. הישיבה בביצות פגעה קשות במצבת כוח האדם של הלגיון ובמהרה צמצמה את כמות הלגיונרים וגרמה לצמצום סד"כ הכוחות שאבטחו את צירי האספקה.
ללגיון הזרים נוצר שם עולם במקסיקו ב-30 באפריל 1863 בהתקלות אשר נודעה בשם קרב קמרון. יחידת הסיור הזעירה בפיקודו של קפיטן דאנז'ו, שכללה 62 חיילים ו-3 קצינים, כותרה ב"חוות קמרון" במקסיקו על ידי חיל הרגלים וחיל הפרשים המקסיקני, שכלל שלושה גדודים (כ-2,000 איש). חרף מצבם הנואש, לחמו אנשי לגיון הזרים כמעט עד האדם האחרון.
קפיטן דאנז'ו נהרג במהלך קרב ההגנה על החווה, וכשאזלה התחמושת לקבוצה שנותרה בחיים הם הסתערו בכידונים שלופים על הצבא המקסיקני. בסופו של דבר נותרו רק שלושה מחיילי הלגיון על הרגלים שהסכימו להיכנע בתנאי שיתאפשר להם לעבור בביטחון, ולשמור על נשקם. המפקד המקסיקני העיר: "אלה לא חיילים, אלה הם שדים", והסכים לבקשתם.
כיום, "יום קמרון" הוא יום חשוב בחגיגות הלגיונרים של לגיון הזרים, ובו מוצגות לראווה היד התותבת של קפיטן דאנז'ו שהוחזרה כמה שנים אחרי הקרב והוענקה על ידי מפקד צבא מקסיקו למפקד הלגיון.
הלגיון נשאר במקסיקו עד לשנת 1870. הוא פונה עם שאר הכוחות הצרפתים עם סיום ההתערבות הצרפתית במקסיקו.
במערכה במקסיקו איבד הלגיון כ-2,000 קצינים וחיילים, כ-1,500 מתוכם בגלל מחלות.
מלחמת צרפת–פרוסיה.
במהלך מלחמת צרפת–פרוסיה ניסה לגיון הזרים להסיר את המצור על פריז, תוך ניסיון להבקיע את הקווים הגרמניים. הלגיון נכשל, ולא הצליח להסיר את המצור מפריז. הלגיון סבל אבדות רבות במהלך המלחמה וסיים אותה עם מניין הרוגים גבוה יותר מכל שאר יחידות צבא צרפת.
הלגיון השתתף בדיכוי הקומונה הפריזאית ובטבח של תושבי פריז. הלגיון הואשם באחריות לטבח על ידי ארגוני שמאל רבים בצרפת אף על פי שהלגיונרים היו מיעוט בכוחות שתקפו את הקומונה והטבח בוצע בהוראת הממשלה בורסאי, האשמה זו נמשכה במשך זמן רב (ב-1970 המפלגה הקומוניסטית הצרפתית המשיכה להאשים את הלגיון באחריות לטבח).
מלחמות קולוניאליות.
במשך הרפובליקה הצרפתית השלישית, שיחק הלגיון תפקיד ראשי בהתפתחות צרפת הקולוניאלית. חייליו נלחמו בצפון אפריקה (שם הקימו כאמור את מפקדתם, בסידי-בל-עבס באלג'יריה), במדגסקר ובהודו-סין, שם הם הובילו את ההשתלטות הצרפתית על האזור. הם עמדו מול כוחות מקומיים שנתמכו על ידי סין. הלגיון לקח חלק גדול בהגנה על טוואן קואנג בשנת 1886.
מלחמות העולם הראשונה.
במלחמת העולם הראשונה נלחם הלגיון קרבות רבים, גורליים וקריטיים, ובכללם קרב ורדן. רבים מן המתנדבים לשורות הלגיון במלחמת העולם הראשונה היו צעירים אמריקנים אשר התנדבו ישר עם פרוץ המלחמה ב-1914. המתנדבים החדשים היו שונים מבחינה איכותית מהלגיונרים הוותיקים, מה שהקשה על שילובם בלגיון. עם כניסת ארצות הברית למלחמה רוב המגויסים האמריקנים שוחררו מן הלגיון כדי שיצטרפו לכוחות האמריקנים. לגיונרים אשר הגיעו ממעצמות הציר (גרמניה, אוסטרו-הונגריה וכו'..) הוצבו בצפון אפריקה כדי למנוע סכנה של מרד או עריקה מצד הלגיונרים.
בין המלחמות.
ב-1932, הלגיון מנה כ-30,000 לגיונרים אשר הוצבו ברחבי האימפריה הקולוניאלית הצרפתית.
כוחות תגבור של הלגיון נשלחו לסוריה עם פרוץ המרד הדרוזי. הם נלחמו בכל הקרבות כנגד המורדים הדרוזים. בעקבות התנאים הגרועים שהלגיונרים קבלו רבים מהם ערקו או ניסו לערוק מן הלגיון.
מלחמת העולם השנייה.
לגיון הזרים היה פעיל מאוד במלחמת העולם השנייה, והוא קיבל תפקיד ראשי במבצעים במזרח התיכון, במערכה במזרח אפריקה ובמבצעים בצפון אפריקה. אחת הבריגדות של הלגיון התפרסה בקרב ביר חכים. חלקה הגדול של הדמי (מחצית) בריגדה ה-13 בפיקודם של ראלף מונקלאר ופייר קניג הייתה היחידה היחידה של לגיון הזרים אשר נענתה לקריאתו של דה גול והצטרפה לכוחות צרפת החופשית, לעומתם רוב הלגיון שמר אמונים לצרפת של וישי. גרמניה לחצה על צרפת של וישי לשחרר את הלגיונרים הגרמנים מהשירות בלגיון. רבים מבין הלגיונרים הגרמנים היו גולים פוליטיים מרחבי הקשת הפוליטית הגרמנית (חלקם היו מהאגף השמאלי של המפלגה הנאצית שחוסל בליל הסכינים הארוכות ויהודים גרמנים רבים) אשר נמלטו מגרמניה הנאצית. היטלר רצה לגייס חלק מהם לצבא הגרמני ואת השאר לשלוח למחנות ריכוז. ממשלת צרפת של וישי סירבה ללחץ הגרמני לבטל את החוזים של הלגיונרים הגרמנים אבל הסכימה לשחרר כל לגיונר שיבחר לעבור לשירות בורמאכט.
ידוע על לפחות מקרה אחד שבו סולק לגיונר יהודי (יליד אוסטריה) משורות הלגיון, בשנת 1942 (לאחר שחרור אלג'יריה על ידי צבא ארצות הברית בשנת 1943 הורשה לחזור לשירות).
הודו-סין.
בעקבות חוסר הפופולריות של המלחמה והתמרמרות אזרחי צרפת עקב דיווחים על כמות ההרוגים הגדולה ממגויסי החובה החליטה ממשלת צרפת שעיקר הכוחות שילחמו בהודו-סין יהיו אנשי הקבע של צבא צרפת ולגיון הזרים. חלק גדול מן הלגיונרים שנשלחו להודו-סין היו חיילים גרמנים לשעבר בוורמאכט. לגיון הזרים היה מעורב בהגנה על דיין ביין פו, ואיבד שם מספר רב של חיילים.
מלחמת אלג'יריה.
מלחמת העצמאות האלג'ירית (1954-62) הייתה טראומטית עבור הלגיון וכמעט גרמה לפירוקו. הלוחמה כנגד "החזית לשחרור לאומי" ו"צבא השחרור הלאומי" (ALN) הייתה אכזרית וקשה, ולוחמים רבים פיתחו כעס כאשר ממשלת צרפת בראשות שארל דה גול כנשיא הודיע על עזיבת אלג'יריה. מספר גנרלים ניצלו את התמרמרותם של הלגיונרים כשהם ניסו לבצע מהפכה צבאית. הם השתמשו בגדוד המוצנח הזר הראשון כדי להשתלט על אלג'יריה אך הניסיון נכשל. לאחר כישלון המרד דה גול התכונן לסגור את לגיון הזרים עקב השימוש בהם בניסיון ההפיכה ולבסוף הוא חזר בו, אך צמצם את סד"כ כוח האדם של הלגיון.
לאחר עזיבת אלג'יריה.
לאחר הקמת אלג'יריה והתנתקותה מצרפת מפקדת הלגיון עקרה למושבה הנוכחי בעיר אבויין בדרום צרפת. גורם זה, בנוסף לפירוק יחידות העלית של הלגיון ועצירה וכליאה של קצינים, נגדים ולגיונרים רבים גרמו ירידה קשה במורל ועריקה רבה. כאשר הנשיא דה גול הכריז בסופו של דבר שהלגיון לא יפורק, והגביל את מצבת כוח האדם ל-8,000 איש ללא ציוד צבאי כבד, המורל בלגיון התמתן.
הלגיון קיבל תפקיד חדש ואורגן ככוח התערבות אשר ניתן לשלוח אותו לכל מקום על פני כדור הארץ במהירות.
מלחמת המפרץ.
בספטמבר 1990, גדוד הפרשים הזרים הראשון, גדוד הזרים השני וגדוד ההנדסה הזרים השני נשלחו למפרץ הפרסי כחלק ממבצע "צבי" (בצרפתית Opération Daguet). הם היו חלק מאוגדת השריון הקלה השישית הצרפתית. עם תחילת הפלישה לעיראק הלגיונרים כבשו את שדה התעופה אל-סלאם, תחת התנגדות קלה. מלבד זאת, הלגיון כמעט ולא פעל בעיראק.
הרכב הלגיון.
מרבית קציני הלגיון הם קצינים צרפתים ממונים. עם זאת, כ-10% מהקצינים הם הלגיונרים שטיפסו בסולם הדרגות עד שהגיעו לדרגתם הנוכחית. שאר הלגיון מורכב מאנשים ממגוון רחב של נתינויות, כאשר חיילי הלגיון שהם בעלי נתינות צרפתית הם 25%-35% מהלגיונרים. המתנדבים הזרים הם בעיקרם אירופאים. באמצע שנות ה-80 של המאה ה-20, זכה הלגיון לתגבורות גדולות של חיילים מבריטניה ומסרביה.