Enteroaggregative Escherichia coli (EAEC) is an important agent that causes endemic and epidemic diarrhoeal diseases worldwide. Several EAEC virulence-related genes (VRGs) have been described but their role in the clinical outcome of infection is not completely defined. This study investigated the prevalence of EAEC and potential associations of its VRGs with risk of or protection from diarrhoeal diseases in children from urban communities in north-eastern Brazil. The case-control study included 166 children, who had their stools evaluated for the EAEC diagnostic genes (aaiC and aatA) using PCR. Positive samples were further analysed by multiplex PCR and identified 18 VRGs. EAEC was found in the same proportion in both groups (41%). The plasmid-borne gene encoding a hexosyltransferase homologue (capU) was the most frequently detected (89.6%), followed by dispersin protein (aap, 58.2%) and EAEC HilA homologue (eilA, 57.8%). The AAF/III fimbrial subunit (agg3A) gene was observed at lower frequency (1.5%). Plasmid-encoded toxin (pet) or AAF/II fimbrial subunit (aafA) was associated significantly with disease. AAF/IV fimbrial subunit (agg4A) or hypothetical plasmid-encoded haemolysin (orf61) was detected significantly more in controls than in children with diarrhoea. In addition, one set of genes in combination, aaiC and agg3/4C but lacking agg4A and orf61, was associated with diarrhoea cases; and another one, orf61 in the absence of pet and aafA, was correlated with control children. These data confirm a high prevalence, endemicity and heterogeneity of EAEC strains in the developing urban areas of north-eastern Brazil. Statistical correlation between cases and controls was seen with either isolated or combined sets of genes, suggesting that the pathophysiology of EAEC infection involves a complex and dynamic modulation of several VRGs.