Enterotoxigenic Escherichia coli (ETEC) is a leading cause of death due to diarrheal illness among young children in developing countries, and there is currently no effective vaccine. Many elements of ETEC pathogenesis are still poorly defined. Here we demonstrate that YghJ, a secreted ETEC antigen identified in immunoproteomic studies using convalescent patient sera, is required for efficient access to small intestinal enterocytes and for the optimal delivery of heat-labile toxin (LT). Furthermore, YghJ is a highly conserved metalloprotease that influences intestinal colonization of ETEC by degrading the major mucins in the small intestine, MUC2 and MUC3. Genes encoding YghJ and its cognate type II secretion system (T2SS), which also secretes LT, are highly conserved in ETEC and exist in other enteric pathogens, including other diarrheagenic E. coli and Vibrio cholerae bacteria, suggesting that this mucin-degrading enzyme may represent a shared virulence feature of these important pathogens.