E. coli is an inhabitant of the gastrointestinal (GI) tracts of warm-blooded animals. It is conventionally believed that E. coli lacks the ability to survive in the external environment. In the previous study, a group of E. coli named UNISED was retrieved from the marine intertidal sediment in Hong Kong, which was demonstrated genetically distinct from the animal host associated E. coli.. However, it is not clear to what extent UNISED is divergent from the animal host associated E. coli, and how different evolutionary forces contributed to the formation of UNISED. Hence, we investigated the genetic and phenotypic relation of isolates of UNISED and their animal host associated counterparts, and explored the population genetics of E. coli from the two sources. Our findings revealed the existence of “Environment-specific” E. coli at both genetic and phenotypic level, suggesting that E. coli of UNISED may adapt to the marine sediment. It was found that mutation and purifying natural selection is important to the formation of the “Environment-specific” E. coli population. However, as current bacterial typing methods cannot totally fulfill our requirements on resolution and the coverage of genomic information of research on E. coli at strain level, a novel shotgun proteomics-based method was developed for the bacterial strain level characterization. Totally, 73 E. coli isolates pertaining to four species of warm-blooded animals were used as testing organisms for this prove-of-principle research. Our findings suggested that this shotgun proteomics-based method is potential to work as an effective tool for bacterial strain level characterization.