Constructing heterostructures with advanced architectures is an effective strategy for enhancing the crystallinity and functional performance of covalent organic frameworks (COFs). Herein, a novel core-shell heterostructure integrating a metal-organic framework (MOF)-derived graphitic carbon core (GC) and a well-arranged COF shell, termed MOF-GC@COF, is reported. ZIF-67 dodecahedra are first chemically etched with a weak organic acid and further converted to MOF-GC via thermal pyrolysis. In the subsequent step, β-ketoenamine-linked COF nanofibers are vertically assembled on the surface of the MOF-GC cores to generate the MOF-GC@COF heterostructure. As a proof-of-concept application, the as-prepared MOF-GC@COF heterostructure is used as an effective quartz crystal microbalance (QCM) sensor for the adsorption of formaldehyde. Benefiting from the synergistic effect of the hybrid composition and the advantages of the core-shell heterostructure, the newly prepared MOF-GC@COF heterostructure exhibits excellent sensing performance toward formaldehyde with rapid adsorption kinetics, high sensitivity, and superior selectivity.