Trade and colonization caused an unprecedented increase in Mediterranean human mobility in the first millennium BCE. Often seen as a dividing force, warfare is in fact another catalyst of culture contact. We provide insight into the demographic dynamics of ancient warfare by reporting genome-wide data from fifth-century soldiers who fought for the army of the Greek Sicilian colony of Himera, along with representatives of the civilian population, nearby indigenous settlements, and 96 present-day individuals from Italy and Greece. Unlike the rest of the sample, many soldiers had ancestral origins in northern Europe, the Steppe, and the Caucasus. Integrating genetic, archaeological, isotopic, and historical data, these results illustrate the significant role mercenaries played in ancient Greek armies and highlight how participation in war contributed to continental-scale human mobility in the Classical world.