The Phoenicians emerged in the Northern Levant around 1800 BCE and by the 9th century BCE had spread their culture across the Mediterranean Basin, establishing trading posts, and settlements in various European Mediterranean and North African locations. Despite their widespread influence, what is known of the Phoenicians comes from what was written about them by the Greeks and Egyptians. In this study, we investigate the extent of Phoenician integration with the Sardinian communities they settled. We present 14 new ancient mitogenome sequences from pre-Phoenician (~1800 BCE) and Phoenician (~700–400 BCE) samples from Lebanon (n = 4) and Sardinia (n = 10) and compare these with 87 new complete mitogenomes from modern Lebanese and 21 recently published pre-Phoenician ancient mitogenomes from Sardinia to investigate the population dynamics of the Phoenician (Punic) site of Monte Sirai, in southern Sardinia. Our results indicate evidence of continuity of some lineages from pre-Phoenician populations suggesting integration of indigenous Sardinians in the Monte Sirai Phoenician community. We also find evidence of the arrival of new, unique mitochondrial lineages, indicating the movement of women from sites in the Near East or North Africa to Sardinia, but also possibly from non-Mediterranean populations and the likely movement of women from Europe to Phoenician sites in Lebanon. Combined, this evidence suggests female mobility and genetic diversity in Phoenician communities, reflecting the inclusive and multicultural nature of Phoenician society.