Но главное, вокруг ЕО сформировалась мощная объединяющая военные и экономические интересы корпоративная империя — холдинг Strategic Resources Corporation, в который в период ее расцвета входили более 50 различных фирм с широким спектром и не только военных услуг — туристическое бюро, чартерная авиакомпания, компания программного обеспечения и многое другое. ЕО же стала небольшой, но отлично подготовленной и прекрасно экипированной частной армией для этой империи.
Executive Outcomes была основана Лютером Эбеном Барлоу в Претории в 1989 году. Он родился в британской Северной Родезии, его семья эмигрировала в ЮАР. В 1974 году Барлоу поступил на службу в инженерные части Сил обороны ЮАР. После перехода в 32-й батальон специального назначения «Баффало», проводивший операции в Анголе и Намибии, в 1981–1983 годах он прошел специальную подготовку по программе британской САС в джунглях Малайзии и быстро дослужился до заместителя командира батальона по разведке. Вернувшись домой, работал в военной разведке до 1986 года, участвовал в тайных операциях в Мозамбике. Затем Барлоу еще три года был главой европейского отдела разведслужбы ССВ (Бюро гражданского сотрудничества), специализирующегося на диверсиях и саботаже. Считается, что ЕО Барлоу создал для того, что проводить в интересах ССВ операции по поставкам вооружений в ЮАР в обход международного эмбарго.
Но политическая ситуация с завершением холодной войны стремительно менялась. Режим апартеида был обречен. Поэтому первыми клиентами ЕО стали ранчеры, которым нужна была защита от браконьеров. Но и армия предоставляла небольшие контракты на тренировку отдельных подразделений. В это время Барлоу написал руководство по саботажу и тайным операциям.
Фортуна улыбнулась ЕО в 1993 году, когда друг Барлоу, бывший офицер САС Саймон Манн предложил ему решить проблему другого его приятеля — хозяина нефтедобывающей компании Heritage Group и бывшего бойца британского спецназа Тони Бэкингема, занимавшегося шельфовыми нефтеразработками в Анголе. Грешивший в юности пацифизмом выпускник Итона и Королевской военной академии в Сэндхерсте Саймон Манн служил в Шотландской гвардии и САС (командир эскадрона), сделал впечатляющую военную карьеру, но вышел в отставку в 1985 году и занялся бизнесом. Но Манн не смог перебороть свою склонность к авантюрам, что в итоге привело его к печальному концу. Но об этом позже.
Повстанцы движения УНИТА захватили центр района нефтедобычи порт Сойо (провинция Заире) на северо-западе страны, и Бэкингем начал нести убытки. Попытки договориться с повстанцами успеха не имели. Правительство Анголы также отказалось выбивать отряды УНИТА из Сойо, так как не имело для этого подготовленных частей.