CYLD was originally identified as the human familial cylindromatosis tumor suppressor. Recently, it was reported that CYLD directly interacts with NEMO/IKKgamma and TRAF2 in the NF-kappaB signaling pathway. The two proteins bind to a region of CYLD that contains a Cys-box motif and the third cytoskeleton-associated protein-glycine conserved (CAP-Gly) domain. Here we report that the third CAP-Gly domain of CYLD specifically interacts with one of the two proline-rich sequences of NEMO/IKKgamma. The tertiary structure of the CAP-Gly domain shares the five-stranded beta sheet topology with the SH3 domain, which is well known as a proline-rich sequence-recognition domain. However, chemical shift mapping revealed that the peptide binding site of the CAP-Gly domain is formed without the long peptide binding loop characteristic of the SH3 domain. Therefore, CAP-Gly is likely to be a novel proline-rich sequence binding domain with a mechanism different from that of the SH3 domain.