In the past decade, traditional yeast two-hybrid techniques have identified a plethora of interactions among soluble proteins operating within diverse cellular pathways. The discovery of associations between membrane proteins by genetic approaches, on the other hand, is less well established due to technical limitations. Recently, a split-ubiquitin system was developed to overcome this barrier, but so far, this system has been limited to the analysis of known membrane protein interactions. Here, we constructed unique split-ubiquitin-linked cDNA libraries and provide details for implementing this system to screen for binding partners of a bait protein, in this case BAP31. BAP31 is a resident integral protein of the endoplasmic reticulum, where it operates as a chaperone or cargo receptor and regulator of apoptosis. Here we describe a novel human member of the protein tyrosine phosphatase-like B (PTPLB) family, an integral protein of the endoplasmic reticulum membrane with four membrane-spanning alpha helices, as a BAP31-interacting protein. PTPLB turns over rapidly through degradation by the proteasome system. Comparisons of mouse cells with a deletion of Bap31 or reconstituted with human BAP31 indicate that BAP31 is required to maintain PTPLB, consistent with a chaperone or quality control function for BAP31 in the endoplasmic reticulum membrane.