Rhomboid intramembrane proteases initiate cell signaling during Drosophila development and Providencia bacterial growth by cleaving transmembrane ligand precursors. We have determined how specificity is achieved: Drosophila Rhomboid-1 is a site-specific protease that recognizes its substrate Spitz by a small region of the Spitz transmembrane domain (TMD). This substrate motif is necessary and sufficient for cleavage and is composed of residues known to disrupt helices. Rhomboids from diverse organisms including bacteria and vertebrates recognize the same substrate motif, suggesting that they use a universal targeting strategy. We used this information to search for other rhomboid substrates and identified a family of adhesion proteins from the human parasite Toxoplasma gondii, the TMDs of which were efficient substrates for rhomboid proteases. Intramembrane cleavage of these proteins is required for host cell invasion. These results provide an explanation of how rhomboid proteases achieve specificity, and allow some rhomboid substrates to be predicted from sequence information.