Регентша Мария Кристина щедро присваивает полковнику Бернею звание «полевого маршала», но на этом забота о легионе и заканчивается. Высокий испанский чин мало трогает французского полковника: его солдат плохо кормят, а в изношенной форме они выглядят как нищие. «Полевой маршал» бомбардирует Париж и Мадрид депешами, но в ответ получает только мудрые советы, например: легионеры должны бережнее относиться к своему обмундированию. В итоге обносившиеся солдаты ходят вместо прохудившихся киверов в трофейных черных беретах, а вместо дырявых сапог — в испанских сандалиях «альпаргатас» на веревочной подошве.

Организаторское новаторство полковника Бернея никто не оценил, а вот его докучливость вызвала глубокое раздражение. «Отца солдат» отзывают, и на его место прибывает полковник Конрад. Испанцы немедленно дают ему кличку «Герой на белом коне».

Вот уже два года в Пиренеях воюет легион голодных оборванцев. Некоторые солдаты переходят на сторону карлистов. К ужасу офицеров, бывает, что во время затишья легионеры встречаются на ничейной земле, перекуривают, справляются о судьбе товарищей, угощают друг друга вином из фляжек, что потом не мешает тем и другим доблестно воевать. Правда, в своих они не целятся… В одной из таких стычек под Барбастро меткий выстрел сбивает полковника Конрада с белого коня. Он становится первым командиром Иностранного легиона, «погибшим на глазах у своих солдат». Его портрет открывает портретную галерею командиров-героев в Музее Иностранного легиона во французском городе Обань. Такая смерть — на виду у всех — считается в легионе высокой честью.

Остатки легиона стягиваются в Памплону. Еще полгода они сидят без денег и провианта. Легион тает на глазах: болезни, инфекции и дезертирство. Только пять сотен уцелевших возвращаются во Францию. Потери: 28 офицеров, 98 унтер-офицеров и 977 легионеров. Это самые большие потери легиона за всю его историю, если не брать в расчет Первую мировую войну. Похоже, план парижских властителей избавиться от нежелательных элементов общества удался на славу! Там, где перемешаны политика, дипломатия и пушки, военных всегда предают — вот весь итог боевого похода.

В Испании продолжается война, но завоевания Алжира никто не отменял. По просьбе Тьера король Луи Филипп 16 декабря 1835 года подписывает указ о создании нового Иностранного легиона. Четыре новых батальона отправляются в Алжир. Все они сформированы по принципу «сплава наций».

Помимо летучей армии Абд аль-Кадира, которого легион считает своим личным врагом, в горах Атласа приходится сражаться с племенами кабилов.

Обе стороны ведут войну без правил: алжирцы убивают пленных, французы душат дымом шесть сотен человек, укрывшихся в пещере, в том числе женщин и детей. Сжигают непокорные деревни, уничтожают урожай, вырубают сады… И в то же время в Алжир едут первые колонисты, нередко — республиканцы, которым претит жизнь в стране «короля лавочников». В 1847 году в Алжире уже 109 тысяч европейцев, половина из них — французы. Для их детей Алжир становится настоящей родиной. Франция где-то там, вдалеке, за морем…

Легионеры не только воюют. Осушают малярийные болота возле Алжира, прокладывают дороги, пробивают тоннели и перебрасывают мосты через горные ущелья. Все это делается не только ради «цивилизации»: современные коммуникации позволят завоевать Кабилию и другие внутренние районы все еще дикой страны.

Полковник Карбуччиа из Второго пехотного полка устраивает свой штаб на месте Ламбеса — древней столицы Нумидии. В свободное от войны время солдаты ведут археологические раскопки: так из-под земли возникает римский мавзолей командующего третьим легионом. Новые легионеры в торжественной обстановке воздают ему воинские почести, считая себя его потомками.

Легионеры впервые меняют форму — вместо тяжелых черных киверов — красные каскетки. Затылок прикрыт от солнца куском белой ткани. Красные брюки и синий короткий мундир. В 1837 году в батальоны начинает поступать новое стрелковое вооружение: капсюльные карабины и мушкетоны.

В 1837 году начинается осада города Константины на востоке Алжира — оплота сопротивления французам. Первый приступ в конце 1836 года был легко отбит. У алжирцев артиллерия: 63 орудия. Их обслуживают турки. К тому же сама природа постаралась, чтобы сделать из Константины неприступную крепость: она расположена на отвесных скалах. К Константине подошли 20 тысяч солдат и артиллерия. После недолгой артиллерийской дуэли французы бросаются на штурм. Легион идет впереди. Личное мужество лейтенанта Ахилла Леруа де Сент-Арно спасает исход дела на одном из участков наступления — когда атака готова вот-вот захлебнуться из-за отчаянного сопротивления арабов, он увлекает за собой своих легионеров. Пуля убивает смельчака наповал, но штурмующие уже смяли сопротивление.

Уличные бои идут до самого вечера: алжирцы бьются за каждую улицу, за каждый дом. В сумерках старший сержант Доз захватывает последнее знамя противника. Город пал… Жители стараются спастись бегством и сотнями погибают в ущельях вокруг города. Победители берут пленных, но неохотно: до наших дней женщины в Константине носят черное покрывало хаик вместо привычного белого: в память о том трагическом дне.

В Алжире остается непокоренной лишь горная Кабилия. В 1856 году легионеры отправляются в горный поход. О них в шутку говорят: «У легионера должны быть ноги козла, сердце льва и желудок муравья».

Применяется новая тактика: легионеры карабкаются по склону, где засели кабилы, и не отвечают на их выстрелы. Пороховой дым действует как дымовая завеса. Оказавшись на гребне, в ход идут штыки и тесаки. После удачной и жестокой военной кампании удается достичь соглашения с горцами: французы будут уважать племенные законы кабилов, а те не будут нападать на пришельцев. Свое соглашение обе стороны не нарушали сто лет.

В 1852 году во Французском Иностранном легионе уже три полка. Большинство солдат — немцы. Офицеры — французы. В январе 1854 года приходит приказ: откомандировать от каждого полка по три батальона для экспедиции в Россию. По мнению парижских стратегов, присутствие легиона в России толкнет угнетенных поляков к массовому дезертирству из русской армии. Так начинается третье путешествие легиона.

Изменился головной убор легионеров, теперь это красное мягкое кепи линейной пехоты с черным квадратным козырьком и номером полка. Офицеры — в синих мундирах, на манер длинных сюртуков. Солдатам выдают синие шинели с пелериной, капюшоном и шестью кожаными пуговицами. Такую шинель вскоре назовут «крымчанкой». На вооружении — современные капсюльные ружья образца 1853 года. А вот ботинки во время затяжной осады быстро износятся, и находчивые легионеры переобуются в деревянные крестьянские башмаки сабо и обмотают ноги «русскими носками» — соломой. Вязаные шерстяные шлемы «Балаклава», которыми они утеплят голову, сохранятся до наших дней в спецподразделениях. На животе у солдат — зарядная сумка «Африка», благодаря ей русские начнут называть легионеров «кожаным брюхом». В армии союзников отряд легионеров получит прозвище «овощная бригада» — они научатся мастерски красть с полей капусту и все съедобное, что найдется в окрестностях стойкого Севастополя.

Но все это впереди — а пока 4,5 тысячи легионеров оживленно грузятся на корабли на причалах Алжира и вместе со всеми армиями Европы отправляются на короткую и победоносную Восточную войну — «проучить зарвавшегося русского царя». В штабных донесениях союзных войск легионеров именуют «Иностранной бригадой».

Но с самого начала все идет не по плану. Уже на Галлипольском полуострове в Турции войска косит эпидемия холеры. Англичанка Флорис Найтингейл разворачивает госпиталь, но болезнь уносит жизни двух сотен легионеров. Как раньше говорили в легионе: «Француз ложится в госпиталь обследоваться, стрелок — вылечиться, а легионер для того, чтобы умереть».