Uropathogenic Escherichia coli (UPEC) strains, which cause the majority of uncomplicated urinary tract infections (UTIs), carry a unique assortment of virulence or fitness genes. However, no single defining set of virulence or fitness genes has been found in all strains of UPEC, making the differentiation between UPEC and fecal commensal strains of E. coli difficult without the use of animal models of infection or phylogenetic grouping. In the present study, we consider three broad categories of virulence factors simultaneously to better define a combination of virulence factors that predicts success in the urinary tract. A total of 314 strains of E. coli, representing isolates from fecal samples, asymptomatic bacteriuria, complicated UTIs, and uncomplicated bladder and kidney infections, were assessed by multiplex PCR for the presence of 15 virulence or fitness genes encoding adhesins, toxins, and iron acquisition systems. The results confirm previous reports of gene prevalence among isolates from different clinical settings and identify several new patterns of gene associations. One gene, tosA, a putative repeat-in-toxin (RTX) homolog, is present in 11% of fecal strains but 25% of urinary isolates. Whereas tosA-positive strains carry an unusually high number (11.2) of the 15 virulence or fitness genes, tosA-negative strains have an average of only 5.4 virulence or fitness genes. The presence of tosA was predictive of successful colonization of a murine model of infection, even among fecal isolates, and can be used as a marker of pathogenic strains of UPEC within a distinct subset of the B2 lineage. IMPORTANCE Escherichia coli is the primary cause of urinary tract infections, the most common bacterial infection of humans. Virulence of a uropathogenic strain is typically defined by the clinical source of the isolate, the ability to colonize the bladder and kidneys in a murine model, the phylogenetic group of the bacterium, and virulence gene content. Here we describe a novel single gene, the repeat-in-toxin gene tosA, the presence of which predicts virulence of E. coli isolates regardless of source. Rapid identification of uropathogenic strains of E. coli may aid in the development of therapeutic and preventive therapies.