Dark matter detectors with directional sensitivity have the capability to distinguish dark matter induced nuclear recoils from isotropic backgrounds, thus providing a smoking gun signature for dark matter in the Galactic halo. Motivated by recent progress in graphene and two-dimensional materials research, we propose a novel class of directional dark matter detectors utilizing graphene-based van der Waals heterostructures. A conceptual design of the detector based on graphene/hexagonal boron nitride and graphene/molybdenum disulfide heterostructures is developed and analyzed. The proposed detector has modular scalability, keV-scale detection threshold, nanometer position resolution, sensitivity down to 10 GeV/c^2 dark matter mass, and intrinsic head-tail discrimination and background rejection capabilities.