Mice carrying a truncated form of cAMP-responsive element binding protein (CREB)-binding protein (CBP) show several developmental abnormalities similar to patients with Rubinstein-Taybi syndrome (RTS). RTS patients suffer from mental retardation, whereas long-term memory formation is defective in mutant CBP mice. A critical role for cAMP signaling during CREB-dependent long-term memory formation appears to be evolutionarily conserved. From this observation, we reasoned that drugs that modulate CREB function by enhancing cAMP signaling might yield an effective treatment for the memory defect(s) of CBP+/- mice. To this end, we designed a cell-based drug screen and discovered inhibitors of phosphodiesterase 4 (PDE4) to be particularly effective enhancers of CREB function. We extend previous behavioral observations by showing that CBP+/- mutants have impaired long-term memory but normal learning and short-term memory in an object recognition task. We demonstrate that the prototypical PDE4 inhibitor, rolipram, and a novel one (HT0712) abolish the long-term memory defect of CBP+/- mice. Importantly, the genetic lesion in CBP acts specifically to shift the dose sensitivity for HT0712 to enhance memory formation, which conveys molecular specificity on the drug's mechanism of action. Our results suggest that PDE4 inhibitors may be used to treat the cognitive dysfunction of RTS patients.