Воскресший легион был отправлен в Алжир в 1837 году и сразу же вступил в битвы за древний город Константина. Созданный еще за 3000 лет до новой эры под названием Кирти, город был реконструирован римским императором Константином в 311 г. и был переименован в его честь. Построенная на скале высотой 600 метров крепость веками считалась неприступной. Под управлением Ахмед-Бея, город устоял перед атаками французов в 1836 году. В начале 1837 года французские колониальные войска были усилены за двумя батальонами легионеров, а в октябре того же года, Иностранный легион уже воюет плечом к плечу с зуавами — добровольцами из кабильских племен, живущих на территории Марокко и Алжира, включенных в колониальную армию в 1830 году. Вместе им удалось сделать немыслимое — проделать лазейку в стене крепости, и проникнуть в древний город. В то время как защитники Константины пытались организовать отчаянное сопротивление, Ахмед-бей улизнул из крепости. После ожесточенных атак солдаты бея были вытеснены улица за улицей, и в конце концов последний крупный город в Алжире оказался под властью французов.

Для Легиона Константин это только начало серии славных битвах после возвращения в Алжир. В 1839 году легионеры овладели и крепостью Джиджели, которая находилась под контролем османских корсаров еще с XVI века, когда она была завоевана Кэр-эд-Дином, известным в Европе под именем Барбаросса.

Отважные воины-легионеры прославились и как строители. Они построили каменную дорогу между городами Дуэро и Буфарик, которая долго называлась «Шоссе Легиона».

Иностранный легион продолжал приобретать все большую известность, и в 1841 году число добровольцев значительно возросло. Таким образом, из воскресшего после войны в Испании Легиона формируются два иностранных полка. Первый стал основателем Дома-матери Иностранного легиона в Сиди-Бель-Аббесе, а второй поддерживал французское военное присутствие в портовом городе Бонн. Эти два полка принимают участие во всех военных операциях в Алжире и не раз и не два удерживали славные победы. В 1847 году герцог Домаль руководил легионерами при подавлении восстания в области Лезоресе. Он был четвертым сыном Луи-Филиппа и Марии-Амели Бурбонской, и в том же году был признан губернатором французских колоний в Африке.

Под Заатчой легионерам противостоял более серьезный соперник в лице шейха Бу Зиан, прославившегося еще в 1833 году, когда его 4000 повстанцев отбили армию Ахмед-Бея. Бу Зиан называл себя вождем — потомком Мухаммеда и повел повстанцев из пустыни на «Священную войну». Кровопролитие продолжалось семь месяцев, и 26 ноября 1849 года решающая битва была выиграна с помощью Легиона и Зуавов. Бу Зиан попал в руки французов, и перед расстрелом, крикнул в небо: «Вы были сильнее, и если на то воля Аллаха, да будет так!» В полночь все минареты города были взорваны.

* * *

В 1853 году началась Крымская война. В основе конфликта стояло желание Николая I, который хотел установить контроль над Святой Землей в Иерусалиме, которая в то время принадлежала Османской империи. Русский царь не предусмотрел, однако, то, что в феврале 1854 года французский император Наполеон III и королева Великобритании Виктория стали союзниками султана. Таким образом, после 700 лет непрерывных конфликтов французы и англичане в первый раз сражались плечом к плечу. Настоящей трудностью для союзников, однако, оказалась тяжелая русская зима. Еще в сентябре 1854 года, холод в окопах остановил объединенные войска Османской империи, Великобритании и Франции. Тогда Наполеон III вспомнил о своем Иностранном легионе, и Первый иностранный полк был вызван помочь в атаках против России.

Во время суровой зимы в окопах под Севастополем Рафаэль Виено был человеком, который подбадривал легионеров и был вместе с ними в самые трудные моменты войны.

Полковник Виено окончил французскую военную академию «Сен-Сир», которая является аналогом американского Вест-Пойнта. Ему было пятьдесят, когда он принял командование Первого иностранного полка и повел его воевать в Крыму. 14 ноября 1854 года, ураган утопил многие французские корабли, перевозящие одежду, амуниции, корм, провиант и все необходимое для осады. Потеря этого драгоценного груза еще более осложнила жизнь солдат. В течение этих месяцев ожидания весны главным врагом легионеров и остальных бойцов союзной армии была холера. В отличие от других, легионеры не имели права жаловаться и, молча, несли свою ношу. Их командир, старый и закаленный воин, который повел их смело уже при первых сражениях. Полковник Виено был примером мужественного воина и постоянно поднимал дух своих солдат.

Сплоченные вокруг своего командира, легионеры штурмовали редут Шварца в ночь на первое мая. Русские отступили, а Первый иностранный полк покрыл себя славой, но его командир остался на поле боя навсегда. Рафаэль Виено, встав как всегда, во главе атаки, был сражен несколькими вражескими пулями. Его именем была названа казарма в Сиди-Бель-Аббесе, а позже и Дом-мать Иностранного легиона в Обани. Сегодня казарма имени Виено является центр вербовки для кандидатов со всего мира, давая им шанс стать легионерами. В июне 1854 года командующим бригады Легиона становится племянник императора, Пьер Бонапарт, который уже проявил себя как командир Второго иностранного полка. Русский генерал Франц Тотлебен защищал Севастополь до августа 1855 года, когда легионеры становятся первыми, которые входят в город. Легионерам могли бы заслужить гораздо больше уважения и медалей, если бы после успешной атаки и вторжения в Севастополь не доказали то, что они и гуляки, и пьяницы. Страсть их к вину и веселью показала их пиратский норов, и они снова завоевали славу безумно храбрых наемников и сорвиголов. Севастополь помнит бесспорный героизм легионеров, но не забывает и о тоннах спиртного, выпитых в честь победы солдатами.

В этой войне приняли участие некоторые из величайших фигур в истории Легиона. Кроме Пьера Бонапарта и полковника Виено, следует отметить, генерала Карбучия, полковника Шабриера, Виталис-Пашу, капитана Мена и незабываемого героя Камерона капитана Данжу.

Генерал Карбучия происходил из знатной семьи на Корсике. Движимый стремлением к военной карьере, он окончил «Сен-Сир» и всего лишь в 19 был включен в пехоту. Он вступает в состав колониальных войск еще в самом начале завоевания Алжира, а позднее его выдающиеся качества воина дали ему право взять на себя командование Второго иностранного полка Легиона. Карбучия с неслыханной смелостью вел своих солдат только к победам. Он проявил храбрость во многих битвах, и его имя остается связанным с завоеванием Алжира, но он получает признание и в другой области, что удивительно для всех — в археологии. Полковник Карбучия и его легионеры обнаружили древнюю столицу Нумидии и раскопали руины древнего города Ламбезис, оккупированного со II по IV века Третьим легионом Августа. По стопам своих предшественников из римских легионов Второй иностранный полк во главе с полковником восстанавливает контуры древней римской провинции.

В 1854 г. Жан-Люк Карбучия отправился на Крымскую войну, в чине генерал-майор бригады легионеров, но в том же году он заразился холерой и умер около Галлиполи.

Полковник де Шабриер, как большинство офицеров в Легионе, окончил военное училище «Сен-Сир». В июне 1855 года он был включен в ряды Второго иностранного полка под Севастополем. После Крымской войны де Шабриер остался в его рядах, и в 1857 году, принял командование им во время экспедиции в Алжире. Под Ишидереном полковник де Шабриер повел Второй иностранный полк к победе. Ему французская армия обязана и успехом миссии в Кабилии, возглавляемой маршалом Рандоном. Два года спустя де Шабриер присоединяется к генералу Макмахону, во время войны в Италии, где им пришлось воевать с австрийцами, во главе с маршалом Ференцем Дюла. В то время как Макмахон завоевал известность и стал герцогом Мадженты, Де Шабриер заслужил уважение своих солдат. Всегда уважаемый в Легионе, Анри Луи Мари-де-Гран-Лакроа де Шабриер пал в битве под Маджентой в 1859 г., но легионеры не забыли его. Сегодня казарма Второго пехотного полка армии в Ниме носит его имя.