Graphitized carbon black (GCB) has been employed for extraction of several classes of analytes, due to the large surface area and the unique chemistry of its surface groups that allows for extracting a wide range of analytes, including polar, acidic compounds. Despite the fact that structurally related materials, such as graphene, found application as hybrid-components in phosphoproteomics, surprisingly, GCB has never been used for the selective enrichment of phosphopeptides. For this purpose, in the present work we used GCB to prepare a magnetic composite with TiO2 (mGCB@TiO2) that was then applied to yeast total extracts. We exploited the high surface area provided by nanostructures, the presence of nano-TiO2 for selective binding of phosphopeptides, and the magnetic responsiveness of magnetite for solid-phase separation. The material was extensively characterized at each modification step by transmission electron microscopy, Fourier-transformed infrared spectroscopy, thermogravimetric analysis, Raman spectroscopy, and porosimetry. Next, the new system was applied for the enrichment of casein phosphopeptides from a simulated tryptic digest with bovine serum albumin (BSA:casein, 100:1). Finally, after assessing the potential applicability, the composite was employed for enriching phosphopeptides from yeast protein digests. This allowed us not only to optimize the enrichment protocol but also to fully compare its performance to commercial TiO2 spin columns. To achieve this aim, the optimized enrichment protocol was included in a typical shotgun proteomics analytical workflow based on nanoHPLC-MS/MS analysis.