The first historically verifiable reference to Carthaginian military activity occurs in 535 BC when city forces with the Etruscans meet the Greeks of Phocaea in a sea battle off Corsica. It is around this time in historical accounts concerning General Mago and his descendants that we have the first concerete documentation of Carthaginian army and its make up. Under the Magonids, who held sway from circa 550 to 400 BC, the city's armed forces were composed primarily of foreign contingents drawn from the various subject states within the Carthaginian realm. Before then, the army is thought to have been largely a citizen levy backed up by tributary allies.
Contingents included: Libyans (largest foreign contingent), Sardinians, Iberians, Liby-Phoenicians, Numidians, Mauri, and various other mercenaries including Italians, Celts, Sicilian Greeks.
While the Carthaginian army drew heavily upon native conscripts from subject territories such as Libya and Sardinia, hired mercenaries played an increasingly important role. By the battle of Himera in 480 BC, they are clearly present in substantial numbers. As ancient sources reveal, these mercenaries were often recruited from warlike peoples like the gauls and Campanians.