CbpA is one of the six E. coli DnaJ/Hsp40 homologues of DnaK co-chaperones and the only one that is additionally regulated by a small protein CbpM, conserved in γ-proteobacteria. CbpM inhibits the co-chaperone and DNA binding activities of CbpA. This regulatory function of CbpM is accomplished through reversible interaction with the N-terminal J-domain of CbpA, which is essential for the interaction with DnaK. CbpM is highly specific for CbpA and does not bind DnaJ despite the high degree of structural and functional similarity between the J-domains of CbpA and DnaJ. Here we report the crystal structure of the complex of CbpM with the J-domain of CbpA. CbpM forms dimers and the J-domain of CbpA interacts with both CbpM subunits. The CbpM-binding surface of CbpA is highly overlapping with the CbpA interface for DnaK, providing a competitive model for regulation through forming mutually exclusive complexes. The structure also provides the explanation for the strict specificity of CbpM for CbpA, which we confirmed by making mutants of DnaJ that became regulated by CbpM. Interestingly, the structure of CbpM reveals a striking similarity to members of the MerR family of transcriptional regulators, suggesting an evolutionary connection between the functionally distinct bacterial co-chaperone regulator CbpM and the transcription regulator HspR.