Human protein kinase X (PrKX) is a cAMP-dependent protein kinase encoded by X chromosome. However, few substrates have been identified so far. To identify the substrates of PrKX, we employed a yeast two-hybrid screen using PrKX as the bait. The human protein MBD4 was isolated as a strong interaction partner. The stability and specificity of interaction were confirmed by in vitro pull-down experiments and immunoprecipitation of complexes assembled in vivo. Subsequently, we showed that the hMBD4 protein expressed in E. coli could be phosphorylated by PrKX. Phosphorylation of hMBD4 by PrKX modulated the binding activity of hMBD4 to fully methylated DNA. These results indicate that MBD4 is a substrate for PrKX.