Protein-protein interactions are typically identified by either biochemical purification coupled to mass spectrometry or genetic approaches exemplified by the yeast two-hybrid assay; however, neither assay works well for the identification of cofactors for poorly soluble proteins. Solubility of a poorly soluble protein is thought to increase upon cofactor binding, possibly by masking otherwise exposed hydrophobic domains. We have exploited this notion to develop a high-throughput genetic screen to identify interacting partners of an insoluble protein fused to chloramphenicol acetyltransferase by monitoring the survival of bacteria in the presence of a drug. In addition to presenting proof-of-principle experiments, we apply this screen to activation-induced cytidine deaminase (AID), a poorly soluble protein that is essential for antibody diversification. We identify a unique cofactor, RING finger protein 126 (RNF126), verify its interaction by traditional techniques, and show that it has functional consequences as RNF126 is able to ubiquitylate AID. Our results underpin the value of this screening technique and suggest a unique form of AID regulation involving RNF126 and ubiquitylation.