Сын ветерана Первой мировой войны, летчика знаменитой эскадрильи барона фон Рихтгофена Рольф Штайнер семь лет отслужил в Иностранном легионе, воевал в Индокитае, Алжире, вступил в ОАС и стал командиром одного из секторов этой подпольной организации. В каждой газетной статье о Штайнере обязательно упоминалось, что в годы Второй мировой войны он служил в «Гитле-рюгенде», что было неверно. Родившийся в 1933 году Рольф Штайнер просто не мог попасть туда по возрасту (в 1945 году ему было 12 лет), он был членом детской организации «Юнгфольк», как и все немецкие школьники его возраста тогда.
Штайнер никогда не считал себя наемником и утверждал в своей автобиографии «Последний искатель приключений», что не получал в Биафре никакого жалования, только деньги на содержание своих частей. Идеалист и крестоносец, он решил сделать полноценную военную карьеру в Биафре и даже получил гражданство этой страны. Умелое руководство Рольфа Штайнера войсками на фронте под Эну-гу в январе 1968 года произвело неизгладимое впечатление на президента Оджукву, который произвел бывшего сержанта Легиона в майоры и разрешил сформировать элитную группу коммандос, отлично показавшую себя в боях. Однако это подразделение было фактически уничтожено из-за ошибок биафрских командиров. После проигранного сражения за Абагану из 120 коммандос Штайнера осталось в живых только шесть. Но он с разрешения президента Биафры сформировал батальон коммандос из 1200 бойцов.
В начале апреля Оджукву поручил Штайнеру сформировать 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 написал тогда: «Им нужен еще один, чтобы создать хорошее название для фильма (намек на «Великолепную семерку» — ее герои тоже были наемниками, дравшимися за правое дело), и сотни, чтобы создать армию».