The first recored use of mercenaries dates back to Ancient Egypt, 1500 BC, when Pharaoh Razmez II used 10,000 mercenaries during his battles.

Xerxes I, king of Persia, who invaded Greece in 484 BC employed Greek mercenaries. The best remembered is Demaratus, for his warning to Xerxes not to underestimate the Spartans before the Battle of Thermopylae.

In Anabasis, Xenophon recounts how Cyrus the Younger hired a large army of Greek mercenaries (the "Ten Thousand") in 401 BC to seize the throne of Persia from his brother, Artaxerxes II. Though Cyrus' army was victorious at the Battle of Cunaxa, Cyrus himself was killed in battle and the expedition rendered moot. Stranded deep in enemy territory, the Spartan general Clearchus and most of the other Greek generals were subsequently killed by treachery. Xenophon played an instrumental role in encouraging "The Ten Thousand" Greek army to march north to the Black Sea in an epic fighting retreat.

Memnon of Rhodes (380–333 BC): was the commander of the Greek mercenaries working for the Persian King Darius III when Alexander the Great of Macedonia invaded Persia in 334 BC and won the Battle of the Granicus River. Alexander also employed Greek mercenaries during his campaigns. These were men who fought for him directly and not those who fought in city-state units attached to his army.

Carthage contracted Balearic Islands shepherds as slingshooters during the Punic wars against Rome. The vast majority of the Carthaginian military - except the highest officers, the navy, and the home guard - were mercenaries.

The Sons of Mars were Italian mercenaries used by the Greek kings of Syracuse until after the Punic Wars.

In the late Roman Empire, it became increasingly difficult for Emperors and generals to raise military units from the citizenry for various reasons: lack of manpower, lack of time available for training, lack of materials, and, inevitably, political considerations. Therefore, beginning in the late 4th century, the empire often contracted whole bands of barbarians either within the legions or as autonomous foederati. The barbarians were Romanized and surviving veterans were established in areas requiring population. The Varangian Guard of the Eastern Roman Empire otherwise known as the Byzantine Empire is the best known formation made up of barbarian mercenaries. (see next section)

Byzantine Emperors followed the Roman practise and contracted foreigners especially for their personal corps guard called the Varangian Guard. They were chosen among war-prone peoples, of whom the Varangians (Vikings) and Anglo-Saxons were preferred. Their mission was to protect the Emperor and Empire and since they did not have links to the Greeks, they were expected to be ready to suppress rebellions. One of the most famous guards was the future king Harald III of Norway, also known as Harald Hardrada ("Hardreign") who arrived in Constantinople in 1035, was employed as a Varangian Guard. He participated in eighteen battles and became Akolythos, the commander, of the Guard before returning home in 1043. He was killed at the Battle of Stamford Bridge in 1066 when his army was defeated by an English army commanded by King Harold Godwinson.

During the ages of the Taifa kingdoms of the Iberian peninsula, Christian knights like the Cid could fight for some Muslim ruler against his Christian or Muslim enemies.

The Almogavares fought for Catalonia and Aragon but in their expedition to Orient, they followed Roger de Flor in the service of the Byzantine Empire.

During the later middle ages, Free Companies (or Free Lances) were formed, consisting of companies of mercenary troops. Nation-states lacked the funds needed to maintain standing forces, so they tended to hire free companies to serve in their armies during wartime. Such companies typically formed at the ends of periods of conflict, when men-at-arms were no longer needed by their respective governments. The veteran soldiers thus looked for other forms of employment, often becoming mercenaries. Free Companies would often specialize in forms of combat that required longer periods of training that was not available in the from of a mobilized militia.

Swiss mercenaries were sought after during the latter half of the 15th century as being an effective fighting force, until their somewhat rigid battle formations became vulnerable to arquebuses and artillery being developed at about that period.

It was then that the European landsknechts, colorful mercenaries with a redoubtable reputation, took over the Swiss forces' legacy and became the most formidable force of the late 15th and throughout the 16th century, being hired by all the powers in Europe and often fighting at opposite sides.

At approximately the same period, Niccolò Machiavelli argued against the use of mercenary armies in his masterpiece The Prince. His rationale was that since the sole motivation of mercenaries is their pay, they will not be inclined to take the kind of risks that can turn the tide of a battle, but may cost them their lives. He believed, logically, that citizens with a real attachement to their home country will be more motivated to defend it and thus make much better soldiers.

In the 20th century, mercenaries have been mostly involved in conflicts on the continent of Africa. There have been a number of unsavory incidents in the brushfire wars of Africa, some involving recruitment of naïve European and American men "looking for adventure" and thrusting them into combat situations where they would not survive to get paid.

Many of the adventurers in Africa who have been described as mercenaries were in fact ideologically motivated to support particular governments, and would not fight "for the highest bidder."

It is known that mercenaries have been hired to fight in the conflicts in former Yugoslavia. Many of these were ex-Eastern Bloc soldiers who had no employment opportunities after the fall of the Soviet Union.

The war in Afghanistan was also fuelled by more than 50 000 voluntaries from other countries. These “muslim” warriors were not really mercenaries as their prime interest was not religion but faith (“holy war”).