Prince, who sold Blackwater in 2010 after it was involved in killings and scandals in Iraq, went to Abu Dhabi, capital of the Persian Gulf federation, in 2011.
He signed on to form an 800-man battalion of mercenaries for what emirati officials termed "anti-terrorism operations" inside and outside the country.
But it's widely believed in Gulf security circles the force, being assembled under considerable secrecy by Prince's Reflex Responses registered in the emirates, will be used for undisclosed special operations for the seven desert emirates that make up the federation.
That's expected to include putting down "internal unrest" that might challenge the ruling families, as happened in Egypt, Libya, Tunisia and Yemen, and which is growing in Kuwait and Bahrain.
The Reflex Responses force, which is officially described in a contract leaked to the New York Times in 2011 as "independent of formal command and support structures throughout the United Arab Emirates," will have its own air wing, with fixed wing aircraft and helicopters, plus its own private navy.
The naval wing's tasks will primarily be "small boat operations ... maritime interdiction operations and securing oil delivery platforms."
The mercenaries have a custom-built high-security base in the desert where troops live and train.
U.S. military analyst Spencer Ackerman says Prince's new project "might run afoul of U.S. laws prohibiting citizens from training foreign militaries," which requires a government license. The State Department has not said whether Reflex Responses has one.
But it's unlikely that Prince, who sold off Blackwater amid a blizzard of adverse publicity over his men's excesses in Iraq where the company was accused of wantonly killing civilians, would embark on this new project without making sure he wasn't open to legal action, particularly if he found himself having to send troops to fight Muslims seeking sweeping democratic reform from rulers who are U.S. allies.
The Sunni Muslim Arab monarchies of the gulf are increasingly concerned about their future amid the political upheaval and conflict sweeping the Arab world, fueled, they claim, by Shiite Iran.
The emirates currently are trying 94 citizens for sedition and seeking to overthrow the political system. The defendants, including two prominent human rights lawyers, face a possible 15 years in prison.
But the over-riding security threat is widely perceived to be Iran, 100 miles across the gulf and which occupies several islands claimed by the Emirates.
Prince's mercenary force is made up largely of Colombian soldiers, including senior officers and men with a Special Forces background
There are also many veterans of Executive Outcomes, a South African security firm that became notorious in the 1990s for suppressing rebellions in mineral-rich African dictatorships and staging coups to gain control of such assets.
EO personnel included many veterans of Britain's Special Air Service and special operations units in South Africa's apartheid-era military.
Prince, an ex-U.S. Navy SEAL, is setting up his new force under a reputed $529 million contract with the royal family of oil-rich Abu Dhabi, the emirates' leader and economic powerhouse. The contract expires in 2015.
Analysts say soldiers from Colombia's 450,000-strong U.S.-trained military are held in high regard in the emirates and other gulf states because of their combat experience fighting leftist guerrillas and because they're not as expensive as Western veterans.
Colombian officials estimate 500 soldiers, including pilots of Black Hawk helicopters widely used in special operations, have gone to join Prince's force, where they earn $3,000 a month against $600 back home.
Bogota has complained to Abu Dhabi to stop hiring its best soldiers, so far without any apparent result.
"These are soldiers with a lot of experience, and it took a great effort to train them," Jorge Bedoya,Colombia's deputy defense minister, told The Financial Times.
The gulf monarchies are used to paying foreigners to do their dirty work. They have traditionally hired foreigners, mainly Pakistanis and Baluchis, to stiffen their armed forces.