
イラクのクウェート侵攻で始まった湾岸戦争はPMC誕生の契機となった。中東地域に展開した多国籍軍は大動員による人員不足を痛感し、米国では軍事アウトソーシング化の研究が開始される。中心となったのが当時国防長官のチェイニー現副大統領であった。彼は政権交代後、米ハリバートン社のCEOとなったが同社はイラク戦争における軍事支援業務で莫大な利益を得ている。
南アフリカでは国際圧力によりアパルトヘイトが撤廃されマンデラ氏により黒人政府が樹立される。その為、長期間続いた周辺国との紛争は終了、政権交代により軍、警察から白人が大量離脱する。南ア特殊部隊は長期間に及ぶ周辺国との紛争によって独自の発展を遂げ、その能力は高く評価されていた。そして南ア特殊部隊、警察軍出身者によりPMCの先駆け「エグゼクティブアウトカムズ」が設立される。同社は主にアフリカ周辺国の紛争において「軍事コンサルタント業務」を請け負うが、直接戦闘にも参加している。反政府軍の攻勢により転覆寸前のシエラレオネにおいて少数部隊で敵を撃退阻止した。この時の報酬は鉱山だったと言われている。
また、アンゴラからの依頼により軍の再編、訓練を行い再建に成功。続いてのアンゴラからの依頼は反政府組織UNITA撃退であった。UNITAは旧南ア白人政権が支援した組織であり、南ア特殊部隊、南ア警察軍特殊部隊が支援共同作戦を行っていた。エグゼクティブアウトカムズは嘗ての同胞を撃退する依頼を受け、UNITAと直接戦闘を行いアンゴラ内での支配地域奪還に成功。UNITA撃滅に貢献した(UNITAは支配地域のダイヤモンド鉱山を失う事で弱体化した)。
その後エグゼクティブアウトカムズは南アにおいて非合法組織と認定され会社は解体するが活動期間で得た利益は多く、後のPMCに多大な影響と教訓を残した。同社が以前の傭兵部隊と違うのは
1. 完全な会社組織の形態をとっており「契約」に基づいた業務請負。
2. 顧客は国家の正式な政府や企業であり、反政府組織や非合法団体からの依頼は受けない。
3. 業務は正式な雇用契約を交わした「社員」により行われ高額な報酬、保険が約束されている。
現在の大手PMCにはエグゼクティブアウトカムズをモデルとして設立されたり警備コンサルタントから業務拡大、転換を図ったものが多く存在する。(エグゼクティブアウトカムズの装備は旧東側の物が大半を占め、それらはソ連崩壊により放出されたものであった。Mil8ヘリ、BPM2歩兵戦闘車等も保有していた。ここでも余剰兵器が紛争に投入された事になる。)