The sexually transmitted pathogen Neisseria gonorrhoeae is regarded as being on the way to becoming an untreatable superbug. Despite its clinical importance, little is known about its emergence and evolution, and how this corresponds with the introduction of antimicrobials. We present a genome-based phylogeographical analysis of 419 gonococcal isolates from across the globe. Results indicate that modern gonococci originated in Europe or Africa, possibly as late as the sixteenth century and subsequently disseminated globally. We provide evidence that the modern gonococcal population has been shaped by antimicrobial treatment of sexually transmitted infections as well as other infections, leading to the emergence of two major lineages with different evolutionary strategies. The well-described multidrug-resistant lineage is associated with high rates of homologous recombination and infection in high-risk sexual networks. A second, multisusceptible lineage is more associated with heterosexual networks, with potential implications for infection control.