Cytolethal distending toxins (CDT) are potent cytotoxins of several Gram-negative pathogenic bacteria, including Escherichia coli, in which five types (CDT-I to CDT-V) have been identified so far. CDT-V is frequently associated with Shiga-toxigenic E. coli (STEC), enterohemorrhagic E. coli (EHEC) O157 strains, and strains not fitting any established pathotypes. In this study, we were the first to sequence and annotate a 31.2-kb-long, noninducible P2-like prophage carrying the cdt-V operon from an stx- and eae-negative E. coli O157:H43 strain of bovine origin. The cdt-V operon is integrated in the place of the tin and old phage immunity genes (termed the TO region) of the prophage, and the prophage itself is integrated into the bacterial chromosome between the housekeeping genes cpxP and fieF. The presence of P2-like genes (n = 20) was investigated in a further five CDT-V-positive bovine E. coli O157 strains of various serotypes, three EHEC O157:NM strains, four strains expressing other variants of CDT, and eight CDT-negative strains. All but one CDT-V-positive atypical O157 strain uniformly carried all the investigated genomic regions of P2-like phages, while the EHEC O157 strains missed three regions and the CDT-V-negative strains carried only a few P2-like sequences. Our results suggest that P2-like phages play a role in the dissemination of cdt-V between E. coli O157 strains and that after integration into the bacterial chromosome, they adapted to the respective hosts and became temperate.