Escherichia coli is a major cause of bloodstream and urinary tract infections globally. The wide dissemination of multi-drug resistant (MDR) strains of extra-intestinal pathogenic E. coli (ExPEC) poses a rapidly increasing public health burden due to narrowed treatment options and increased risk of failure to clear an infection. Here, we present a detailed population genomic analysis of the ExPEC ST131 clone, in which we seek explanations for its success as an emerging pathogenic strain beyond the acquisition of antimicrobial resistance (AMR) genes. We show evidence for evolution towards separate ecological niches for the main clades of ST131 and differential evolution of anaerobic metabolism, key colonisation and virulence factors. We further demonstrate that negative frequency-dependent selection acting across accessory loci is a major mechanism that has shaped the population evolution of this pathogen.