FimH, the type 1 pilus adhesin of uropathogenic Escherichia coli (UPEC), contains a receptor-binding domain with an acidic binding pocket specific for mannose. The fim operon, and thus type 1 pilus production, is under transcriptional control via phase variation of an invertible promoter element. FimH is critical during urinary tract infection for mediating colonization and invasion of the bladder epithelium and establishment of intracellular bacterial communities (IBCs). In silico analysis of FimH gene sequences from 279 E. coli strains identified specific amino acids evolving under positive selection outside of its mannose-binding pocket. Mutating two of these residues (A27V/V163A) had no effect on phase variation, pilus assembly, or mannose binding in vitro. However, compared to wild-type, this double mutant strain exhibited a 10,000-fold reduction in mouse bladder colonization 24 h after inoculation and was unable to form IBCs even though it bound normally to mannosylated receptors in the urothelium. In contrast, the single A62S mutation altered phase variation, reducing the proportion of piliated cells, reduced mannose binding 8-fold, and decreased bladder colonization 30-fold in vivo compared to wild-type. A phase-locked ON A62S mutant restored virulence to wild-type levels even though in vitro mannose binding remained impaired. Thus, positive selection analysis of FimH has separated mannose binding from in vivo fitness, suggesting that IBC formation is critical for successful infection of the mammalian bladder, providing support for more general use of in silico positive selection analysis to define the molecular underpinnings of bacterial pathogenesis.