Cattle harbor Shiga toxin-producing Escherichia coli (STEC) in their intestinal tract, thereby providing these microorganisms with an ecological niche, but without this colonization leading to any clinical signs. In a preceding study, genotypic characterization of bovine STEC isolates unveiled that their ability to colonize cattle persistently (STECper) or only sporadically (STECspo) is more closely associated with the overall composition of the accessory rather than the core genome. However, the colonization pattern could not be unequivocally linked to the possession of classical virulence genes. This study aimed at assessing, therefore, if the presence of certain phenotypic traits in the strains determines their colonization pattern and if these can be traced back to distinctive genetic features. STECspo strains produced significantly more biofilm than STECper when incubated at lower temperatures. Key substrates, the metabolism of which showed a significant association with colonization type, were glyoxylic acid and L-rhamnose, which were utilized by STECspo, but not or only by some STECper. Genomic sequences of the respective glc and rha operons contained mutations and frameshifts in uptake and/or regulatory genes, particularly in STECper. These findings suggest that STECspo conserved features leveraging survival in the environment, whereas the acquisition of a persistent colonization phenotype in the cattle reservoir was accompanied by the loss of metabolic properties and genomic mutations in the underlying genetic pathways.