Укрепленный лагерь в центре вражеской территории — сомнительное дело, особенно если учесть, что снабжение приходилось осуществлять только воздушным путем. При планировке поясов обороны и размещении артиллерии было совершено много вопиющих ошибок, например, оставили без контроля холмы, господствующие над долиной. Французский штаб был убежден, что регулярная вьетнамская армия не сможет доставить в этот район тяжелое вооружение. Они недооценили командующего войсками Вьет Мина генерала Во Нгуен Зиапа, который решил эту задачу и в течение пяти недель 1954 г. перебросил 200 орудий и 4 регулярные дивизии на холмы вокруг Дьен Бьен Фу. Он сумел это сделать, использовав многотысячную массу безымянных носильщиков.

13 марта вьетнамцы открыли огонь и в следующие восемь недель бомбардировки велись непрерывно. Снаряды разрушили летное поле, вынудив французов сбрасывать продовольствие и боеприпасы на парашютах. Это был акт отчаяния, поскольку батареи вьетнамских зенитных орудий сумели сбить или повредить 169 самолетов — почти половину французской авиации. Во время осады в лагерь высаживались батальон за батальоном, хотя было ясно, что сражение проиграно. Солдаты безропотно выполняли приказы благодаря характерному для элитных частей духу солидарности со сражающимися товарищами. В частности, в лагерь высадился 1-й батальон парашютистов, еще в воздухе отвечая гранатами и автоматным огнем на град снарядов врага. Несмотря на большие потери, уже на следующий день легионеры пошли в атаку на форт Элен, который с конца марта находился в руках вьетнамцев. Бой проходил с переменным успехом, и форт несколько раз переходил из рук в руки, но в конце концов был захвачен французами. Через 2 недели второй батальон попытался отбить форт Хюгет, но потерял 150 человек и был объединен в одно подразделение с остатками 1-го батальона.

К 7-му мая массированные атаки Вьет Мина сломили сопротивление Дьен Бьен Фу. Солдаты 15 000-го гарнизона были убиты, ранены или взяты в плен, за исключением 75 человек штабистов. 4 тысячи французских солдат и офицеров были убиты в боях, 11 тысяч попали в плен. Всех вьетнамцев, служивших французам, коммунисты расстреляли. Легионеров из стран Восточной Европы отправили в СССР, где они бесследно исчезли. Остальные сотнями умирали от ран, голода, тропической лихорадки и укусов змей. Домой вернулись только 4 тысячи из 11.

Потери были не столь уж велики, учитывая общую численность французских войск в Индокитае, но они коснулись цвета армии. Глупые решения командования привели к гибели в долине Дьен Бьен Фу почти всех элитных воздушно-десантных частей. Дух французской армии оказался сломлен, войну уже нельзя было выиграть. Несмотря на поражение французов, слава и популярность парашютистов, особенно из Иностранного легиона, достигли всех уголков Франции.

Успех народно-освободительных сил в Индонезии и память о поражении Франции в 1940 г. разожгли огонь вооруженного восстания в Алжире. Его инициатором явился фронт Национального освобождения (ФНО), пользовавшийся поддержкой других арабских стран.

По французским законам Алжир являлся не колонией, а заморским департаментом, т.е. составной частью Франции. Там жили полтора миллиона европейских иммигрантов, в течение нескольких поколений связанных с этой страной. Поначалу повстанцам противостояли 30 тысяч французских солдат и жандармов.

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

Только к концу 1956 г. к действиям приступили парашютисты легиона. Батальоны, сражавшиеся в Индокитае, получили столь высокую оценку руководства, что поредевшие подразделения расширили до полков. Формально 1-й полк парашютистов легиона (1. РЕП) сформировали в июне 1955 г., 2-й — в декабре того же года (из 2-го и 3-го батальонов). Парашютисты этих полков стали самыми опасными противниками ФНО. Уже первый удар 2-го РЕП получил широкий резонанс. Оперировавшие в районе Мезера легионеры использовали безжалостную тактику, разработанную штабом и контрразведкой французских сил в Алжире. Принцип так называемых «полос изоляции» предусматривал превращение зон проникновения ФНО в «запретные» территории. В этих районах населению приказывали немедленно покинуть дома, ликвидировали доставку продовольствия и систему здравоохранения. Армия получала право стрелять без предупреждения в каждого, кто после определенного часа оказывался в запретной полосе, и парашютисты 2-го РЕП охотно пользовались этим. Всего за 3 недели легионеры рапортовали о ликвидации 900 партизан и пленении еще 500. Все эти данные были фикцией — к партизанам, убитым в бою, добавили гражданских лиц, погибших «при невыясненных обстоятельствах». К концу 1956 г. руководство 2-го РЕП сообщило командованию о ликвидации 1440 вооружейных партизан, хотя на склады поступило лишь 140 единиц трофейного оружия.

В конце 1956 г. в Алжир вернулись солдаты 10-й парашютной дивизии, принимавшие участие в операции «Мушкетер» (десант на Суэцкий канал). Генерала Массю и подчиненную ему дивизию разместили в Алжире с задачей восстановить в столице полный порядок (после введения «полос изоляции» алжирцы начали движение городских партизан). Бомбы взрывались в кафе, магазинах, трамваях. Нападали на военные и полицейские патрули. На улицах множились нападения на белых прохожих и на мусульман, сотрудничавших с властями. Министр по делам Алжира Р. Лакост передал в руки генерала Массю всю полицейскую власть в городе, а он, в свою очередь, обязался умиротворить столицу. 7-го января 1957 г. началась «Битва за Алжир». В распоряжении Массю находились 1-й и 3-й полки парашютистов колониальных войск и 1-й полк парашютистов легиона под командованием полковника Жанпьера.

В начале 1957 г. в городе Алжире жили около 250 тысяч мусульман, часть которых бежала туда из районов, разоренных войной и операциями умиротворения. Извилистые улочки арабской Казбы хранили почти все тайны ФНО. Здесь обучали партизан, планировали покушения и изготавливали бомбы. Полиция была не в состоянии справиться с ситуацией, и в дело пошли войска. Легионеры реализовали план «Шампань». Руководил ими майор Фолке, впоследствии король наемников в Черной Африке — безжалостный любитель драк, с лицом, обезображенным ножом. Парашютисты методически окружали кварталы, проводили обыски и массовые аресты. С помощью полиции и секретных агентов был составлен точный список жителей Казбы. Всех арабов без удостоверения личности считали бунтовщиками. Подозреваемых в принадлежности или симпатиях к ФНО арестовывали и допрашивали в нелегальных камерах пыток, организованных на базах парашютистов. Сотни людей прошли через мучения на вилле «Сусини», где 1-й парашютный полк легиона организовал собственную тюрьму. Парашютисты в масках избивали алжирцев и французов, сочувствовавших ФНО, а также журналистов, плохо отзывавшихся об акциях умиротворения. Арестованных топили в ваннах с водой, морили голодом, пытали электрическим током. Всего при облавах и от пыток погибли 2, 5 тысячи человек.