Syphilis, which is caused by the sexually transmitted bacterium Treponema pallidum subsp. pallidum, has an estimated 6.3 million cases worldwide per annum. In the past ten years, the incidence of syphilis has increased by more than 150% in some high-income countries, but the evolution and epidemiology of the epidemic are poorly understood. To characterize the global population structure of T. pallidum, we assembled a geographically and temporally diverse collection of 726 genomes from 626 clinical and 100 laboratory samples collected in 23 countries. We applied phylogenetic analyses and clustering, and found that the global syphilis population comprises just two deeply branching lineages, Nichols and SS14. Both lineages are currently circulating in 12 of the 23 countries sampled. We subdivided T. p. pallidum into 17 distinct sublineages to provide further phylodynamic resolution. Importantly, two Nichols sublineages have expanded clonally across 9 countries contemporaneously with SS14. Moreover, pairwise genome analyses revealed examples of isolates collected within the last 20 years from 14 different countries that had genetically identical core genomes, which might indicate frequent exchange through international transmission. It is striking that most samples collected before 1983 are phylogenetically distinct from more recently isolated sublineages. Using Bayesian temporal analysis, we detected a population bottleneck occurring during the late 1990s, followed by rapid population expansion in the 2000s that was driven by the dominant T. pallidum sublineages circulating today. This expansion may be linked to changing epidemiology, immune evasion or fitness under antimicrobial selection pressure, since many of the contemporary syphilis lineages we have characterized are resistant to macrolides.