1989年に南アフリカ共和国で誕生したエグゼクティブ・アウトカムズ（Executive Outcomes,略称EO）社は、フレデリック・ウィレム・デクラークやネルソン・マンデラ政権下で行われたアパルトヘイト政策の廃止や軍縮によって職を失った兵士を雇用することで、優秀な社員を多数有する会社となった。

特に第32大隊などの精鋭部隊に所属していた黒人兵士を多く雇用していたが、彼らはアンゴラ内戦で家族や財産を失い、逃げ延びた先の南アフリカでは白人達に周辺国への軍事介入や同じ黒人の弾圧に動員され、アパルトヘイト廃止後行き場を失った者達だった（EO社の解体後はポムフレットなど辺境の町で貧しく暮らしている）。

EO社はアンゴラ内戦中の1993年にアンゴラ政府と契約を結び、正規軍の訓練と直接戦闘を実行。結果アンゴラ全面独立民族同盟（UNITA）に壊滅的被害を与えることに成功し、20年続いた内戦をわずか1年で終結させた。その後、国際社会の圧力でアンゴラ政府はEO社との契約を打ち切り、国連が平和維持を行うことになったが平和維持部隊は任務に失敗し、アンゴラは内戦に逆戻りした。

また、シエラレオネ内戦では、残虐な行動と少年兵を利用することで知られた反政府勢力革命統一戦線（RUF）の攻勢で、先に展開したグルカ・セキュリティー・サービス社は司令官であったロバート・C・マッケンジーが殺害されるなど大きな被害を出し撤退、首都フリータウンも陥落寸前の状態であったが、EO社はわずか300人の部隊でRUFに壊滅的被害を与え、RUFが占拠していたダイヤモンド鉱山を奪還することで和平交渉の席に着かせることに成功した。しかし、こちらもアンゴラと同様に内戦に逆戻りした。

EO社は次第に肥大化し、戦闘機、攻撃機、攻撃ヘリコプターなどの航空兵器や、戦車、歩兵戦闘車のような強力な陸上兵器、負傷者輸送用のボーイング707なども運用するようになったが、危機感を抱いた南アフリカ政府によって1998年に解体された。しかし、内戦の戦局をも変えてしまう民間軍事会社の登場は世界に衝撃を与えた。

パプアニューギニアでは、ブーゲンビル紛争（英語版）において、政府が同国のパプアニューギニア国防軍（英語版）よりも民間軍事会社のサンドライン・インターナショナルを重用したため、国軍によるクーデターが発生している。詳細は「w:Sandline affair」を参照
2000年代元グルカ兵のコントラクター（アフガニスタン、ナンガハル州）

1990年代に登場した民間軍事会社は、その後急速に業務を拡大していき、2001年のアメリカ同時多発テロ事件以降からはイラクやアフガニスタンでの活動が注目を集めるようになった。しかし、急速な組織拡大から法規の作成が追いつかず、管理する法律も組織も無い無法状態が続いたため、殺人や虐待など数々の不祥事を起こしてきた。

2001年にはアメリカで民間軍事会社の管理組織であるInternational Peace Operations Associationが発足、2006年にはイギリスでアメリカとは異なる民間軍事会社管理組織であるBritish Association Of Private Security Companiesが発足した。イギリスの場合はアメリカよりも非常に厳格で、民間軍事会社にISOやBSの取得を義務付けておりプレゼンテーションにおいてもイギリスの民間軍事会社はアメリカのそれとは違うことを強調している。

イラクにおける管理組織は連合国暫定当局が行ってきたが解体にともない2004年8月に連合国暫定当局から分離したNPO法人としてPrivate Security Company Association of Iraqが発足した。イラクでは連合国暫定当局が最後に発行したCPA Order17という規定に基づいて行動していたが、この規定は大変に問題のあるもので、民間軍事会社はイラクの法律に従う必要が無く、あらゆる免責特権を認め、税金も免除するなど民間軍事会社を完全に治外法権化する物であった。

2007年9月にはブラックウォーターUSAのコントラクターがイラクで輸送部隊の護衛中に市中で無差別発砲を行いイラク人を17人射殺するという事件が起きると、イラク政府も厳しい措置を取らざるを得なくなり、2009年1月1日でCPA Order17の無効を宣言し、民間軍事会社から免責特権を剥奪した。これ以降、民間軍事会社はイラクの国内法に従う義務が生じPrivate Security Company Association OF Iraqは2009年現在は実質的に活動していない。

このような無法状態を改善しようとする動きもあり、2008年9月17日にスイスのモントルーで17ヶ国によって採択されたモントルー文書で初めて国際的な規制が出来た。指針であり条約ではないため、国際法としての拘束力は無いが、新たな条約締結へ向けた活動が行われている。
2010年代

イラク戦争後、民間軍事会社は各地の小規模紛争に派遣されるようになった。リビア内戦においては、イスラエルのグローバルCSTが主にアフリカ系からなる警備要員や東欧・中東系の戦闘機パイロットなど多数の要員を派遣して非武装市民への殺傷を含む過剰な業務を行い、シリア内戦では、アメリカの民間軍事会社が自由シリア軍など反アサド派を訓練するためにトルコで活動していた。一方、シリア政権側もロシア系の民間軍事会社の先駆けで香港を拠点とするスラヴ軍団から同様の支援を受けていた[6]。アフリカではブラックウォーター社の設立者だったエリック・プリンスらが中国政府系の香港企業フロンティア・サービス・グループで中国の国家戦略である一帯一路を警備面から支援していた[7][8]。