В начале апреля Оджукву поручил Штайнеру сформировать 4-ю десантную бригаду трехтысячного состава (пять батальонов, один из них — морской пехоты). Уильямс и Норбьято стали заместителями командира 4-й бригады. При соединении организовали кустарное производство мин и боеприпасов, а также минометов и даже базук. Батальон морпехов Штайнер разместил в дельте реки Нигер под Калабаром. Под руководством Норбьято они провели несколько успешных нападений на федеральные речные конвои. Один захват был особенно успешен — 2 млн. 7,62-мм патронов и 10 тонн минометных мин.
Бойцы 4-й бригады носили цвета Иностранного легиона — зеленый и красный, зеленые береты. Их девизом стало «Честь и верность». Это было написано на первом штандарте легиона, полученном от короля Луи Филиппа. На парадах чаще исполняли «Марсельезу», а не национальный гимн.
К апрелю ситуация на фронте сложилась критическая. 3-я дивизия федеральных сил полковника Адекунле, в составе которой было два батальона наемников из Чада и группа британских военных советников, вышла в долину реки Кросс, где оборону держал Тэффи Уильямс с несколькими сотнями лично им обученных десантников и семьюстами добровольцами из местных кланов ибо. Но в начале апреля Уильямс отвел своих людей для введения их в состав 4-й бригады и оголил фронт, федералы и чадские наемники переправились через реку, заняли города Орон и Иту, а затем начали захватывать биафрские города один за другим. Соединившись со своим десантом в районе Порт-Харкорта, полковник Адекунле начал наступление на этот стратегический порт. После яростного артиллерийского обстрела нигерийцы 18 мая взяли город. В этом бою пропал без вести (скорее всего, погиб) майор Норбьято.
Через неделю неугомонный Штайнер решил нанести чувствительный удар в самом неожиданном месте — уничтожить вражеский аэродром в Энугу (50 км за линией фронта), где базировались два МиГа и шесть Ильюшиных. В рейд он взял 25 лучших бойцов. Объект охраняли 400 солдат федеральной армии и взвод бронемашин Ferret. Заняв позиции ночью перед аэродромом, коммандос атаковали в 6.15 утра во время утреннего развода. Федералы в панике разбежались под ураганным огнем. Вся авиатехника была уничтожена огнем из гранатометов и крупнокалиберных пулеметов.
Рейды этой бригады удерживали на позициях 2-ю дивизию федералов, не давая ей присоединиться к остальным дивизиям в штурме Иболенда. К концу июля 1968 года 3-я дивизия продвинулась из Порт-Харкорта до Умуахьи в 23 км от Оверри, откуда открывалась прямая дорога на столицу сепаратистов. В Оверри была переброшена 4-я бригада коммандос. Ее командир майор Штайнер занимался оперативным планированием, боевыми же действиями руководил командир ударной группы «Нсукка» майор Уильямс. который постоянно демонстрировал своим подчиненным примеры безрассудного мужества, стоя на переднем крае под огнем, размахивая тростью и посылая подальше нигерийских пулеметчиков. Бойцы его боготворили. К этому моменту к ним присоединились еще трое наемников. Заместителем Штайнера стал его сослуживец по 1-му полку Иностранного легиона тощий, тихий, но крайне опасный корсиканец Арман Ианарелли (капитан Арман), он возглавил ударную группу «Ахоада». Уильямс завербовал молодого родезийца Джона Эразмуса — гения по части взрывчатых веществ и взрывных устройств, который возглавил ударную группу «Аба-лики». Заместителем Уильямса стал коренастый шотландец Алек-садра Гэй, который воевал в отряде Жана Шрамма в Букаву. В июле к бригаде присоединился еще один белый наемник Льюис Малруни, которого все называли Пэдди. Получивший звание капитана бывший инженер Пэдди прожил в Африке 22 года из своих 54, имел в Биафре недвижимость (захваченную на тот момент федералами) и не желал возвращаться в Европу. Всего шесть солдат удачи. Корреспондент France Soir написал тогда: «Им нужен еще один, чтобы создать хорошее название для фильма (намек на «Великолепную семерку» — ее герои тоже были наемниками, дравшимися за правое дело), и сотни, чтобы создать армию».