Phage-inducible chromosomal islands (PICIs) represent a novel and universal class of mobile genetic elements, which have broad impact on bacterial virulence. In spite of their relevance, how the Gram-negative PICIs hijack the phage machinery for their own specific packaging and how they block phage reproduction remains to be determined. Using genetic and structural analyses, we solve the mystery here by showing that the Gram-negative PICIs encode a protein that simultaneously performs these processes. This protein, which we have named Rpp (for redirecting phage packaging), interacts with the phage terminase small subunit, forming a heterocomplex. This complex is unable to recognize the phage DNA, blocking phage packaging, but specifically binds to the PICI genome, promoting PICI packaging. Our studies reveal the mechanism of action that allows PICI dissemination in nature, introducing a new paradigm in the understanding of the biology of pathogenicity islands and therefore of bacterial pathogen evolution.