Напряжение на Ближнем Востоке усилилось, когда президент Насер провозгласил победу Египта над империалистическими силами Запада. Вслед за этим в Ираке группа молодых офицеров убила юного короля Фейсала и его дядю, крон-принца Абдаллу, а призывавшего к спокойствию премьер-министра Нури-Саида разъяренная толпа забила насмерть. Государственный переворот в Ираке затронул Иорданию, партнера Ирака по Арабскому союзу, и 31 июля 1958 года 2000 британских парашютистов приземлились в Аммане, а американские морские пехотинцы высадились в Бейруте. Волна беспорядков прокатилась по всему Ближнему Востоку. Арабские республиканцы остро отреагировали на политическое и экономическое подавление Британией бесчисленных эмиратов, султанатов, монархий и протекторатов.

Единственным обломком колониальной империи, брошенным на чашу весов, остался Аден, которым Британия управляла 28 лет. Последней стратегической базой была крепость в южной оконечности Красного моря, обеспечивавшая доступ к Суэцкому каналу. Эта крохотная территория, контролируемая Британией, оказалась посреди Федерации Южной Аравии, состоявшей из племенных эмиратов южноаравийского побережья Аденского залива. На обширных гористых землях вплоть до Саудовской Аравии разразилась война между финансируемой Советами Народной Республикой Южного Йемена и Федерацией, поддерживаемой Британией.

К 1960 году Аден оказался во враждебном окружении, и последовавшие события задержали 45-й отряд на самый долгий срок в истории коммандос. К ним вскоре присоединились преобразованный САС и подразделение СБС, разместившееся в Бахрейне. СБС прибыл с Мальты в марте 1960 года и занял «лагерь Би-Пи» (BP camp) в Дхале, где и базировался все время своего пребывания в Южной Аравии. Вначале половина отряда оставалась в Дхале, а остальные отправились в отдаленный и безлюдный район Радфан, где впервые после ухода с Кипра вступили в боевые действия, на этот раз с так называемыми арабскими диссидентами. Радфан — почти безводный горный регион в 50 милях к северу от Адена с отдельными воинственными племенами, собиравшими дань с караванов, проходящих по традиционному пути из Дхалы в Йемен. В августе, когда вышел закон о запрещении забастовок, коммандос, патрулировавшие зловонные улочки Адена, впервые почувствовали, что значит исполнять международный долг по поддержанию безопасности. Те трудные первые месяцы были лишь прологом. Коммандос оказались вовлеченными в кровавый кошмар терроризма и партизанской войны в самых суровых природных условиях. Отряд попеременно выполнял задания в Радфане и обеспечивал порядок в Адене, не прекращая тренироваться, чтобы не потерять десантных навыков.

Вдобавок к их бедам, республиканский Ирак положил глаз на богатый нефтью Кувейт и объявил его своей собственностью. Окончание срока британского протектората над этой крошечной страной побудило Ирак к решительным действиям. В июне 1961 года разведка донесла, что иракская армия мобилизована и готова к вторжению; то же самое случится и через 30 лет при Саддаме Хусейне. В июле десантников перебросили по воздуху в Кувейт. Там к ним присоединился 42-й отряд коммандос, прибывший морем из Сингапура, и подразделение № 6 СБС с Мальты. СБС осуществлял береговую разведку на случай десанта крупных сил, однако тысячи трехсот британских морских пехотинцев, патрулировавших улицы Кувейта, хватило, чтобы Ирак отказался от вторжения. Отряд № 45 вернулся в Дхалу к патрульной службе. Столкновения с партизанами участились. Казалось, весь регион стремительно несется к полному распаду, и в ноябре войска промаршировали 80 миль в Аден, где снова приступили к выполнению интернационального долга по обеспечению порядка. Пока они находились в городе, военное командование устроило в Аденском заливе показательные десантные учения с привлечением нового корабля коммандос «Булварк». В этой демонстрации силы 45-й отряд коммандос играл главную роль. Несколько месяцев спустя провели повторные учения с привлечением отрядов № 45, 42 и роты управления 3-й бригады. Еще одни учения в районе Адена провели на следующий год с участием прибывшего морем из Сингапура отряда коммандос № 40 и недавно переформированного отряда № 41, приплывшего из Англии и впервые действовавшего совместно с 3-й бригадой.

Однако вскоре из-за тягот патрульной службы от учений пришлось отказаться. В 1963 году гражданская война в Йемене достигла Радфана, и 45-й отряд снова вызвали туда, усилив парашютистами и САС. Действия в Радфане превратились в длительную операцию с участием британских войсковых соединений: Восточно-Английского полка (East Anglian Regiment) и 39-й бригады. Именно в тот период 45-й отряд начал использовать вертолеты в тактических целях, что имело далеко идущие последствия. В мае 1964 года подполковник Т.М.П. Стивенс в своем рапорте командующему Королевской морской пехотой сообщал: «С 30 апреля по 9 мая мы не снимали одежду, в которой прибыли (наши вещи так нас и не догнали), имели минимум питьевой воды и спали на голых камнях. У каждого бойца было три бутылки с водой, которых хватало на сутки или даже больше, если мало двигаться и находиться в тени. В долгих и трудных ночных маршах те, кто шел с полной выкладкой — связисты, например, — пили много. Никто не получил тепловой удар, но сколько случаев истощения! Вечером, ночью, утром было даже приятно, но дневная жара на голых скалах ужасна. Мы гордились нашими бородами, которые отпустили по необходимости. Мы научились жить и сражаться в тех условиях. А самый главный урок: мы убедились в необыкновенной эффективности нескольких хорошо замаскированных на вершинах снайперов… Также очень важна материально-техническая база, а пополнение ресурсов с вертолетов — важнейший элемент… Действия САС великолепны. Они растворяются среди диссидентов маленькими группами, открывают огонь и наводят артиллерию и самолеты, как только завидят цель».

Не успели коммандос отдохнуть после операций в Радфане и патрулирования Адена, как их перебросили на Танганьику подавлять мятеж, вспыхнувший в армии этой страны. Затем 45-й отряд вернулся в Южную Аравию, где ситуация продолжала ухудшаться. Все больше времени они проводили в горах, получая припасы с вертолетов. Всего за семь недель 45-й отряд коммандос провел 305 ночных патрулей, а в начале 1966 года участвовал в восьми крупных операциях. В одном из последних походов в глубь страны они по подтвержденным данным уничтожили 24 террориста и вскоре первыми из британских военных формирований покинули регион, оставив его в руках парашютистов и 39-й бригады.

Однако уход из Радфана не означал, что отряд № 45 получил передышку, вовсе нет. По соглашению, сформулированному лейбористским правительством Гарольда Вильсона, Аден получал независимость. Контрольный срок полного вывода британских войск был назначен на 1967 год, и 45-й отправился в Аден для обеспечения безопасности в районе Маала, ставшем на время центром гражданских беспорядков. Населению не терпелось поскорее выдворить британцев. В одном из самых крупных столкновений в Адене 45-й отряд уничтожил тринадцать террористов, потеряв одного человека убитым и двоих ранеными. В конце концов коммандос уходили из Адена последними; прикрывали войска, самолетами переправлявшиеся из аэропорта Хормаксар в последние дни британской оккупации Адена. За службу в Аравии 45-й был награжден многими орденами и медалями, включая три «Ордена Британской империи» 3-й степени, два «Военных креста», четыре медали «За заслуги», 6 благодарностей в приказе, три благодарности Королевы и 15 благодарностей Главнокомандующего. За семь лет боевых действий в отряде было убито только 6 человек и 62 ранено, что отметили, как «относительно небольшое количество, учитывая такой срок и тяжесть проведенных операций».

Пока 45-й томился в Южной Аравии, остальные коммандос 3-й бригады сражались во влажных непроходимых джунглях Борнео, в условиях, не менее тяжелых, чем выжженные солнцем горы и пустыни Радфана. Война, стыдливо названная «конфронтацией», вспыхнула, когда пронзительный взгляд «сумасшедшего» доктора Сукарно, президента Индонезии, остановился на британском протекторате на острове Борнео.