Heterostructures play significant roles in modern semiconductor devices and micro/nanosystems in a plethora of applications in electronics, optoelectronics, and transducers. While state-of-the-art heterostructures often involve stacks of crystalline epi-layers each down to a few nanometers thick, the intriguing limit would be heterto-atomic-layer structures. Here we report the first experimental demonstration of freestanding van der Waals heterostructures and their functional nanomechanical devices. By stacking single-layer (1L) MoS2 on top of suspended single-, bi-, tri- and four-layer (1L to 4L) graphene sheets, we realize array of MoS2-graphene heterostructures with varying thickness and size. These heterostructures all exhibit robust nanomechanical resonances in the very high frequency (VHF) band (up to ~100 MHz). We observe that fundamental-mode resonance frequencies of the heterostructure devices fall between the values of graphene and MoS2 devices. Quality (Q) factors of heterostructure resonators are lower than those of graphene but comparable to those of MoS2 devices, suggesting interface damping related to interlayer interactions in the van der Waals heterostructures. This study validates suspended atomic layer heterostructures as an effective device platform and opens opportunities for exploiting mechanically coupled effects and interlayer interactions in such devices.