Cytoplasmic incompatibility (CI) results when Wolbachia bacteria-infected male insects mate with uninfected females, leading to embryonic lethality. "Rescue" of viability occurs if the female harbors the same Wolbachia strain. CI is caused by linked pairs of Wolbachia genes called CI factors (CifA and CifB). The co-evolution of CifA-CifB pairs may account in part for the incompatibility patterns documented in insects infected with different Wolbachia strains, but the molecular mechanisms remain elusive. Here, we use X-ray crystallography and AlphaFold to analyze the CI factors from Wolbachia strain wMel called CidA and CidB . Substituting CidA interface residues with those from CidA (from strain wPip) enables the mutant protein to bind CidB and rescue CidB -induced yeast growth defects, supporting the importance of CifA-CifB interaction in CI rescue. Sequence divergence in CidA and CidB proteins affects their pairwise interactions, which may help explain the complex incompatibility patterns of mosquitoes infected with different wPip strains.