High levels of fecal bacteria are a concern for the aquatic environment, and identifying sources of those bacteria is important for mitigating fecal pollution and preventing waterborne disease. Escherichia coli has been used as an indicator of fecal pollution, however less success has been achieved using this organism for library-independent microbial source tracking. In this study, using next-generation sequencing technology we sequenced the whole genomes of 22 E. coli isolates from known sources (9 from humans, 2 from cows, 6 from pigs, and 5 from chickens) and identified candidate host-specific genomic regions. Specificity testing on the candidate regions was performed using 30 E. coli isolates from each source. Finally, we identified 4 human-, 2 cow-, 3 pig-, and 4 chicken-specific genetic markers useful for source tracking. We also found that a combination of multiplex PCR and dual index sequencing is effective for detecting multiple genetic markers in multiple isolates at one time. This technique was applied to investigating identified genetic markers in 549 E. coli isolates obtained from the Yamato River, Japan. Results indicate that humans constitute a major source of water contamination in the river. However, further work must include isolates obtained from geographically diverse animal hosts to make this method more reliable.