Protein kinases and their substrates comprise extensive signaling networks that regulate many diverse cellular functions. However, methods and techniques to systematically identify kinases directly responsible for specific phosphorylation events have remained elusive. Here we describe a novel proteomic strategy termed fluorescence complementation mass spectrometry (FCMS) to identify kinase-substrate pairs in high throughput. The FCMS strategy employs a specific substrate and a kinase library, both of which are fused with fluorescence complemented protein fragments. Transient and weak kinase-substrate interactions in living cells are stabilized by the association of fluorescence protein fragments. These kinase-substrate pairs are then isolated with high specificity and are identified and quantified by LC-MS. FCMS was applied to the identification of both known and novel kinases of the transcription factor, cAMP response element-binding protein (CREB). Novel CREB kinases were validated by in vitro kinase assays, and the phosphorylation sites were unambiguously located. These results uncovered possible new roles for CREB in multiple important signaling pathways and demonstrated the great potential of this new proteomic strategy.