History of private military companies
Main article: Private Military Corporations
“The mercenaries and auxiliaries are useless and dangerous, and if anyone supports his state by the arms of mercenaries, he will never stand firm or sure, as they are disunited, ambitious, without discipline, faithless, bold amongst friends, cowardly amongst enemies, they have no fear of God, and keep no faith with men,” wrote Machiavelli in The Prince.
As Peter W. Singer says in his book, Corporate Warriors: The Rise of the Privatized Military Industry (ISBN 0801441145), "[T]he monopoly of the state over violence is the exception in world history, rather than the rule. The state itself is a rather new unit of governance, appearing only in the last four hundred years. Moreover, it drew from the private violence market to build its public power."
And as Lt. Col. Tim Spicer says in his book, An Unorthodox Soldier: Peace and War in the Sandline Affair (ISBN 1840183497), "Mercenary soldiering has a long and honorable history...When something is both widespread and long lasting, there must be some fundamental reason for it. In the case of mercenaries, the reasons why they have continued to survive and prosper down the centuries can be reduced to just two: efficiency and technology."
The Peace of Westphalia, signed in 1648, ended The Thirty Years' War and established the exception Peter Singer cites above, the sovereignty of the state and its monopoly over the use of violence.
During the beginning of The Thirty Years War, a Prussian general, Albrecht von Wallenstein, was very successful in raising, training and leasing out huge battalions of soldiers that lived off of plunder and destroyed the countryside of the Holy Roman Empire. Wallenstein was able to forge out a large swath of land for himself in Prussia from his profits. He was assassinated in 1634 as his power became a threat to the Holy Roman Emperor.
The architects of the Peace of Westphalia acknowledged the overwhelming perpetuation of warfare mercenaries created in the Thirty Years War and the previous Hundred Years' War. The treaties making up the Peace began plans to centralize the use of force within the emerging European nations.
Over time there were several results. The first was the birth of the modern standing army and patriotism. The era of The Enlightenment developed new ideas of the social contract, the relationship between citizen, soldier and state. Citizens were more willing to fight than subjects, and thus more reliable than hired soldiers. Citizens also became restricted from fighting in foreign armies. (Singer, pg. 31)
The maintenance of a larger, internal army produced a larger, more complicated tax system, which in turn developed into the modern bureaucratic bodies governing many of the countries around the world. (Singer, pg. 30) New techniques introduced orginally by Prince Maurice of Nassua, borrowing from Roman and Greek training, included extended drilling, marching in cadence, and other forms of discipline which built loyality, a sense of belonging, and a fighting spirit mercenaries could not always be counted on to provide.
The final outcome was the development of diplomacy. War became an extension of diplomacy, the last act of diplomacy, as countries would remain in communications to avoid destroying each other.
However, this did not eliminate the use of hired soldiers. Mercenaries were still used in wars, though considerably less than they had been before. Many were active outside of Europe as privateers and trading companies as they waged wars amongst themselves, against other outposts and outside the realm of diplomacy. But for continental warfare, large, centralized armies became standard, if not overdone. As was said by Marquis de Mirabeau about Prussia a century later, "Prussia is not a state with an army but an army with a state." (Singer, pg. 37)
Thus professional, private soldiering never really went away, and given the rise of regional conflicts after the Cold War, the international community's inability or unwillingness to get involved, and the efforts by large governments to downsize their militaries and rely on technologically sophisticated weapons, it is only logical this market would emerge and determine the many traits of recent, current and future wars.
Background of the private military company
The roots of today's private military companies can be traced back to Captain David Stirling, who founded the Special Air Service in 1941 to fight the Germans in small hard-hitting groups. The unconventional methods of the SAS where successful and they remained a British institution after the war.
David Stirling would go on to found the first 20th century private military company a couple decades later, WatchGuard International in 1967. Watchguard hired from the SAS and was created to train the armies of the Persian Gulf sultanates. 
During the next two decades, mercenary activity in Africa grew and gave the negative reputation to it that followed into the nineties. People like "Mad" Mike Hoare and Bob Denard gained notoriety by overthrowing governments and assassinating leaders. 
Another early company was formed in 1975 when three former SAS officers came together and formed the Control Risks Group. Founder David Walker would go on to form Keenie Meenie Services of Iran-Contra fame, and Saladin Security, which is still in existence. Another founder, Arish Turle, would go onto to form the Risk Advisory Group, who's subsidiary, Janusian, is active in Iraq.
By the 1980's, Margaret Thatcher and Ronald Reagan began efforts to privatize government services. Defence Systems Limited was started in this atmosphere as former members of the SAS got into the military consulting and training business. George Bush as vice-president began to privatize aspects of the intelligence services.
As Secretary of Defense for President Bush, Dick Cheney contracted Brown and Root Services (now KBR) a total of $8.9 million to put together a proposal on how to integrate private companies more effectively into warfare.
These concepts were not new in the US military. Contractors had been used in conjunction with military operations in the Vietnam War as Pacific Architects and Engineers fulfilled duties formerly the responsibility of the Army Corps of Engineers, while Vinnell and Halliburton were providing logistical support and other companies like Cubic, General Dynamics, and Lockheed Martin, have been producing weapons, staff, vehicles, simulators, armor, facilities maintenance, training services, and technology through contracts from the government for years.
The End of the Cold War and the Nineties
When the Cold War ended, the dynamics of the global geopolitical atmosphere changed. Large standing armies became dinosaurs and millions of soldiers spilled into the world marketplace. The end of the South African apartheid regime coupled with the withdrawal of Cold War support from African countries spawned a new generation of mercenary activity on the continent.
The Cold War's end also ended the polarized nature of the world and left many governments weak and neglected by countries that had needed them in a larger strategic battle. This atmosphere is similar to times when hired military services flourished and weak governments relied on their expertise.
In America, Pentagon generals were recognizing the eminent downsizing of the military and Military Professional Resources Inc. was formed. They would soon operate in the Balkan wars, as would DynCorp and Halliburton. Their roles were different though. MPRI was contracted to train the Croatian fighting force while DynCorp and Halliburton were hired for facilities maintenance services.
The nineties also saw the rise of a South African/ Great Britain based firm, Executive Outcomes, which would pave the path, in many ways, for the reputation of the modern private military service provider. They were active through out Africa and greatly influenced by mineral and oil extraction companies. They were operated mostly by officers from the recently dissolved Aparthied regime, and they hired soldiers used before in southern African wars of independence. At their height midway through the decade they were capable of fielding over 1,000 soldiers into battle. Over 90 companies all together were active in Africa in the nineties.
Aside from the Balkans and Africa, PMCs like AirScan and Defence Systems Limited were used in Colombia by oil firms to protect lines from attack while others, like Dyncorp, have been contracted in Plan Colombia to fight the War on Drugs. Sandline International had contracts in Papua New Guinea and Sri Lanka. MPRI even developed their contract to run ROTC recruiting stations on over 200 US college campuses.