Twenty-nine Shiga toxin-producing Escherichia coli (STEC) strains were identified in a collection of 2,607 isolates from patients with diarrhea in São Paulo, Brazil, from 1976 to 1999. The STEC strains belonged mainly to serotypes O111:HNM (HNM, nonmotile) (13 of 29 [44.8%]), O111:H8 (7 of 29 [24%]), and O26:H11 (4 of 29 [13.8%]); stx(1) eae (26 of 29 [89.6%]), in combination with either enterohemorrhagic E. coli hlyA (11 of 26 [42%]) or astA (24 of 26 [92.3%]), prevailed. The O111 STEC strains were distinguished by their inability to decarboxylate lysine. The predominance of STEC O111 and O26 since the late 1970s and the identification of STEC serotypes O55:H19, O93:H19, and O118:H16 in association with human infections in Brazil are described for the first time.