Shiga toxin-producing (Stx) Escherichia coli (STEC) O113:H21 strains are associated with human diarrhea and some of these strains may cause hemolytic uremic syndrome (HUS). The molecular mechanism underlying this capacity and the differential host cell response to HUS-causing strains are not yet completely understood. In Brazil O113:H21 strains are commonly found in cattle but, so far, were not isolated from HUS patients. Here we conducted comparative gene co-expression network (GCN) analyses of two O113:H21 STEC strains: EH41, reference strain, isolated from HUS patient in Australia, and Ec472/01, isolated from cattle feces in Brazil. These strains were cultured in fresh or in Caco-2 cell conditioned media. GCN analyses were also accomplished for cultured Caco-2 cells exposed to EH41 or Ec472/01. Differential transcriptome profiles for EH41 and Ec472/01 were not significantly changed by exposure to fresh or Caco-2 conditioned media. Conversely, global gene expression comparison of both strains cultured in conditioned medium revealed a gene set exclusively expressed in EH41, which includes the dicA putative virulence factor regulator. Network analysis showed that this set of genes constitutes an EH41 specific transcriptional module. PCR analysis in Ec472/01 and in other 10 Brazilian cattle-isolated STEC strains revealed absence of dicA in all these strains. The GCNs of Caco-2 cells exposed to EH41 or to Ec472/01 presented a major transcriptional module containing many hubs related to inflammatory response that was not found in the GCN of control cells. Moreover, EH41 seems to cause gene network dysregulation in Caco-2 as evidenced by the large number of genes with high positive and negative covariance interactions. EH41 grows slowly than Ec472/01 when cultured in Caco-2 conditioned medium and fitness-related genes are hypoexpressed in that strain. Therefore, EH41 virulence may be derived from its capacity for dysregulating enterocyte genome functioning and its enhanced enteric survival due to slow growth.