European starlings (Sturnus vulgaris) represent one of the most widespread and problematic avian invasive species in the world. Understanding their unique population history and current population dynamics can contribute to conservation efforts and clarify how evolutionary processes play out over short timescales. European starlings were introduced to Central Park, New York in 1890, and from a founding group of about 100 birds, they have expanded across North America with a current population of approximately 200 million. There were also multiple introductions in Australia in the mid-19th century, and at least one introduction in South Africa in the late 19th century. Independent introductions on these three continents provide a robust system to investigate invasion genetics. In this study, we compare mitochondrial diversity in European starlings from North America, Australia and South Africa, and a portion of the native range in the United Kingdom. Of the three invasive ranges, the North American population shows the highest haplotype diversity and evidence of both sudden demographic and spatial expansion. Comparatively, the Australian population shows the lowest haplotype diversity, but also shows evidence for sudden demographic and spatial expansion. South Africa is intermediate to the other invasive populations in genetic diversity but does not show evidence of demographic expansion. In previous studies, population genetic structure was found in Australia, but not in South Africa. Here we find no evidence of population structure in North America. Although all invasive populations share haplotypes with the native range, only one haplotype is shared between invasive populations. This suggests these three invasive populations represent independent subsamples of the native range. The structure of the haplotype network implies that the native range sampling does not comprehensively characterize the genetic diversity there. This study represents the most geographically widespread analysis of European starling population genetics to date.