Stl is a master repressor encoded by Staphylococcus aureus pathogenicity islands (SaPIs) that maintains integration of these elements in the bacterial chromosome. After infection or induction of a resident helper phage, SaPIs are de-repressed by specific interactions of phage proteins with Stl. SaPIs have evolved a fascinating mechanism to ensure their promiscuous transfer by targeting structurally unrelated proteins performing identically conserved functions for the phage. Here we decipher the molecular mechanism of this elegant strategy by determining the structure of SaPIbov1 Stl alone and in complex with two structurally unrelated dUTPases from different S. aureus phages. Remarkably, SaPIbov1 Stl has evolved different domains implicated in DNA and partner recognition specificity. This work presents the solved structure of a SaPI repressor protein and the discovery of a modular repressor that acquires multispecificity through domain recruiting. Our results establish the mechanism that allows widespread dissemination of SaPIs in nature.