Neisseria meningitidis (meningococcus) is usually transmitted via respiratory droplets, whereas its close relative, the gonococcus is sexually transmitted. Invasive meningococcal disease due to isolates of serogroup C increased in Europe and the United States among men who have sex with men (MSM). These isolates were also recovered from cases of urethritis suggesting sexual transmission. Genome sequencing of representative strains revealed that isolates from MSM and urethritis cases belonged to a unique clade within clonal complex11. Proteome analysis showed expression of nitrite reductase by these isolates, enabling anaerobic growth as in gonococci. Invasive isolates from MSM, but not urethritis isolates expressed functional human factor H (hfH) binding protein associated with enhanced survival in transgenic mice expressing hfH, a complement regulatory protein. Our data provide a unique example of meningococcal evolution with adaptation to sexual transmissibility, initially associated with low virulence but with subsequent fHbp-associated invasiveness. Implications for vaccination strategies are discussed.