W 1961 sformowano batalion spadochronowy (hiszp. Caballeros Legionaries Paracaidistas). Do 1976 Legia działała na terenie Sahary Hiszpańskiej. Po przekazaniu tej kolonii Mauretanii i Maroku, wycofany z Sahary 3. pułk przeniesiono na Wyspy Kanaryjskie, a 4. pułk rozwiązano. Ostatecznie w 1979 pozostało 10 tysięcy legionistów.
Na początku lat 80. Hiszpańska Legia Cudzoziemska składała się z: 1. Tercio „Gran Capitan” i 2. Tercio „Duque de Alba”, które stacjonowały w Melilli i Ceucie. Składały się one z kompanii dowodzenia i trzech batalionów piechoty 3. Tercio „Juan de Austria”, stacjonujące od 1976 w Fuerteventurze na Wyspach Kanaryjskich. Składało się z kompanii dowodzenia, dwóch batalionów piechoty i Grupy Lekkiej Kawalerii (GLC), która powstała z Grupos Ligeros Saharios (jednostka rozpoznawcza) 4. Tercio „Alejandro Farnesio” (reaktywowane w 1981) stacjonowało w Rondzie. Była to jednostka pomocnicza i składała się z batalionu szkolnego, zapasowego, Szkoły Dowódców (AFML) i Oddziału do Zadań Specjalnych (kompania).