Eeben Barlow lives and works on a quiet, tree-lined side street in a wealthy suburb of Pretoria, the city that was once the headquarters of South Africa’s apartheid military establishment. Set back behind well-tended grounds and a swimming pool, guarded by surveillance cameras and two stone lions at the portico, Barlow’s stately mock-tudor villa could easily belong to a corporate executive in Greenwich, Connecticut. The living room décor would make Martha Stewart proud: heavy-nubbed silk drapes and matching rose-colored leather and brocade love seats, couches, and wing chairs. As Barlow pours coffee into fine china, it is easy to forget that he was once a commander of the notorious 32 Battalion of the South African special forces, but there are several clues scattered about: a small library of spy novels, a collection of battle histories, and the oversized World Encyclopedia of Organized Crime, by Jay Robert Nash, which sits propped up between two golden swans on the lacquered coffee table.

Everything is elegant, orderly, and civil, including the corporate brochure Barlow hands to his guests upon arrival. It’s a glossy black portfolio with multicolor graphics that describe the confidential “advisory,” “training,” and “equipment” services his company, Executive Outcomes, provides: Clandestine Warfare, Combat Air Patrol, Armored Warfare, Basic and Advanced Battle Handling, and Sniper Training. The corporation, the brochure says, prides itself on its flawless and unequaled success record, on its above-average growth rate, and on the five thousand man-years of combat experience of its workforce—all former elite commandos of the apartheid regime. Barlow’s company declares that it is one of the largest businesses of its kind in the world, but that is an easy boast. It is, so far, the only incorporated private mercenary army on earth that will contract to move in and wage full-scale war on behalf of its client.

I visited Barlow at his vill...