Travelers' diarrhea (TD) is the most prevalent illness encountered by deployed military personnel and has a major impact on military operations, from reduced job performance to lost duty days. Frequently, the etiology of TD is unknown and, with underreporting of cases, it is difficult to accurately assess its impact. An increasing number of ailments include an altered or aberrant gut microbiome. To better understand the relationships between long-term deployments and TD, we studied military personnel during two nine-month deployment cycles in 2015-2016 to Honduras. To collect data on the prevalence of diarrhea and impact on duty, a total of 1173 personnel completed questionnaires at the end of their deployment. 56.7% reported reduced performance and 21.1% reported lost duty days. We conducted a passive surveillance study of all cases of diarrhea reporting to the medical unit with 152 total cases and a similar pattern of etiology. Enteroaggregative E. coli (EAEC, 52/152), enterotoxigenic E. coli (ETEC, 50/152), and enteropathogenic E. coli (EPEC, 35/152) were the most prevalent pathogens detected. An active longitudinal surveillance of 67 subjects also identified diarrheagenic E. coli as the primary etiology (7/16 EPEC, 7/16 EAEC, and 6/16 ETEC). Eleven subjects were recruited into a nested longitudinal substudy to examine gut microbiome changes associated with deployment. A 16S rRNA amplicon survey of fecal samples showed differentially abundant baseline taxa for subjects who contracted TD versus those who did not, as well as detection of taxa positively associated with self-reported gastrointestinal distress. Disrupted microbiota was also qualitatively observable for weeks preceding and following the incidents of TD. These findings illustrate the complex etiology of diarrhea amongst military personnel in deployed settings and its impacts on job performance. Potential factors of resistance or susceptibility can provide a foundation for future clinical trials to evaluate prevention and treatment strategies.