Increased mobility and human interactions in the Mediterranean region during the eighth through fifth centuries BCE resulted in heterogeneous communities held together by political and cultural affiliations, periodically engaged in military conflict. Ancient historians write of alliances that aided the Greek Sicilian colony Himera in victory against a Carthaginian army of hired foreign mercenaries in 480 BCE, and the demise of Himera when it fought Carthage again in 409 BCE, this time unaided. Archaeological human remains from the Battles of Himera provide unique opportunities to test early written history by geochemically assessing the geographic origins of ancient Greek fighting forces. We report strontium and oxygen isotope ratios of tooth enamel from 62 Greek soldiers to evaluate the historically-based hypothesis that a coalition of Greek allies saved Himera in 480 BCE, but not in 409 BCE. Among the burials of 480 BCE, approximately two-thirds of the individuals are non-local, whereas among the burials of 409 BCE, only one-quarter are non-local, in support of historical accounts. Although historical accounts specifically mention Sicilian Greek allies aiding Himera, isotopic values of many of the 480 BCE non-locals are consistent with geographic regions beyond Sicily, suggesting Greek tyrants hired foreign mercenaries from more distant places. We describe how the presence of mercenary soldiers confronts prevailing interpretations of traditional Greek values and society. Greek fighting forces reflect the interconnectedness and heterogeneity of communities of the time, rather than culturally similar groups of neighbors fighting for a common cause, unified by "Greekness," as promoted in ancient texts.