We report on the experimental demonstration of atomically thin molybdenum disulfide (MoS2)-graphene van der Waals (vdW) heterostructure nanoelectromechanical resonators with ultrawide frequency tuning. With direct electrostatic gate tuning, these vdW resonators exhibit exceptional tunability, in general, {Delta}f/f0 >200%, for continuously tuning the same device and the same mode (e.g., from ~23 to ~107MHz), up to {Delta}f/f0 = 370%, the largest fractional tuning range in such resonators to date. This remarkable electromechanical resonance tuning is investigated by two different analytical models and finite element simulations. Further, we carefully perform clear control experiments and simulations to elucidate the difference in frequency tuning between heterostructure and single-material resonators. At a given initial strain level, the tuning range depends on the two-dimensional (2D) Youngs moduli of the constitutive crystals; devices built on materials with lower 2D moduli show wider tuning ranges. This study exemplifies that vdW heterostructure resonators can retain unconventionally broad, continuous tuning, which is promising for voltage-controlled, tunable nanosystems.