Intracellular Wolbachia bacteria manipulate arthropod reproduction to promote their own inheritance. The most prevalent mechanism, cytoplasmic incompatibility (CI), traces to a Wolbachia deubiquitylase, CidB, and CidA. CidB has properties of a toxin, while CidA binds CidB and rescues embryonic viability. CidB is also toxic to yeast where we identified both host effects and high-copy suppressors of toxicity. The strongest suppressor was karyopherin-α, a nuclear-import receptor; this required nuclear localization-signal binding. A protein-interaction screen of Drosophila extracts using a substrate-trapping catalytic mutant, CidB*, also identified karyopherin-α; the P32 protamine-histone exchange factor bound as well. When CidB* bound CidA, these host protein interactions disappeared. These associations would place CidB at the zygotic male pronucleus where CI defects first manifest. Overexpression of karyopherin-α, P32, or CidA in female flies suppressed CI. We propose that CidB targets nuclear-protein import and protamine-histone exchange and that CidA rescues embryos by restricting CidB access to its targets.