Uropathogenic Escherichia coli (UPEC) are the major cause of urinary tract infections. Nearly half of all UPEC strains secrete hemolysin, a cytotoxic pore-forming toxin. Here, we show that the prevalence of the hemolysin toxin gene (hlyA) is highly variable among the most common 83 E. coli sequence types represented on the EnteroBase genome database. To explore this diversity in the context of a defined monophyletic lineage, we contextualized sequence variation of the hlyCABD operon within the genealogy of the globally-disseminated multidrug-resistant ST131 clone. We show that sequence changes in hlyCABD and its newly defined 1.616-kb long leader sequence correspond to phylogenetic designation, and that ST131 strains with the strongest hemolytic activity belong to the most extensive multidrug resistance sublineage (clade C2). To define the set of genes involved in hemolysin production, the clade C2 strain S65EC was completely sequenced and subjected to a genome-wide screen by combining saturated transposon mutagenesis and transposon-directed insertion site sequencing with the capacity to lyse red blood cells. Using this unique approach, and subsequent targeted mutagenesis and complementation, 13 genes were confirmed to be specifically required for production of active hemolysin. New hemolysin controlling elements included discrete sets of genes involved in LPS inner-core biosynthesis (waaC, waaF, waaG, rfaE) and cytoplasmic chaperone activity (dnaK, dnaJ), and we show these are required for hemolysin secretion. Overall, this work provides a unique description of hemolysin sequence diversity in a single clonal lineage and describes a complex multi-level system of regulatory control for this important toxin.