Some cdt genes are located within the genome of inducible or cryptic bacteriophages, but there is little information about the mechanisms of cdt transfer because of the reduced number of inducible Cdt phages described. In this study, a new self-inducible Myoviridae Cdt phage (ΦAA91) was isolated from a nonclinical O157:H7 Shiga toxin-producing Escherichia coli strain and was used to lysogenize a cdt-negative strain of Shigella sonnei. We found that the phage induced from S. sonnei (ΦAA91-ss) was not identical to the original phage. ΦAA91-ss was used to infect a collection of 57 bacterial strains, was infectious in 59.6% of the strains, and was able to lysogenize 22.8% of them. The complete sequence of ΦAA91-ss showed a 33,628-bp genome with characteristics of a P2-like phage with the cdt operon located near the cosR site. We found an IS21 element composed of two open reading frames inserted within the cox gene of the phage, causing gene truncation. Truncation of cox does not affect lytic induction but could contribute to phage recombination and generation of lysogens. The IS21 element was not present in the ΦAA91 phage from E. coli, but it was incorporated into the phage genome after its transduction in Shigella. This study shows empirically the evolution of temperate bacteriophages carrying virulence genes after infecting a new host and the generation of a phage population with better lysogenic abilities that would ultimately lead to the emergence of new pathogenic strains.