Urinary tract infections (UTIs) are common in women and recurrence is a major clinical problem. Most UTIs are caused by uropathogenic Escherichia coli (UPEC). UPEC are generally thought to migrate from the gut to the bladder to cause UTI. UPEC strains form specialized intracellular bacterial communities (IBCs) in the bladder urothelium as part of a pathogenic mechanism to establish a foothold during acute stages of infection. Evolutionarily, such a specific adaptation to the bladder environment would be predicted to result in decreased fitness in other habitats, such as the gut. To examine this concept, we characterized 45 E. coli strains isolated from the feces and urine of four otherwise healthy women with recurrent UTIs. Multi-locus sequence typing revealed that two of the patients maintained a clonal population in both of these body habitats throughout their recurrent UTIs, whereas the other two manifested a wholesale shift in the dominant UPEC strain colonizing their urinary tract and gut between UTIs. These results were confirmed when we subjected 26 isolates from two patients, one representing the persistent clonal pattern and the other representing the dynamic population shift, to whole genome sequencing. In vivo competition studies conducted in mouse models of bladder and gut colonization, using isolates taken from one of the patients with a wholesale population shift, and a newly developed SNP-based method for quantifying strains, revealed that the strain that dominated in her last UTI episode had increased fitness in both body habitats relative to the one that dominated in the preceding episodes. Furthermore, increased fitness was correlated with differences in the strains’ gene repertoires and their in vitro carbohydrate and amino acid utilization profiles. Thus, UPEC appear capable of persisting in both the gut and urinary tract without a fitness tradeoff. Determination of all of the potential reservoirs for UPEC strains that cause recurrent UTI will require additional longitudinal studies of the type described in this report, with sampling of multiple body habitats during and between episodes.