Modeling and design of innovative materials and ultrasmall structures are nowadays a topic of major interest in engineering science, due to the recent advancements in nanoscience and nanotechnology. A plethora of current applications involve nanostructures interacting with elastic media which show significant size effects. This study investigates dynamics of nanobeams resting on nonlocal foundations. The constitutive law relating elastic flexural curvature and bending interaction fields is expressed according to a stress-driven spatial convolution. The interaction between beam and surrounding medium is modelled according to a displacement driven spatial convolution. The issues related to the Eringen–Wieghardt nonlocal approach are thus bypassed by exploiting a consistent methodology leading to well-posed structural problems. The relevant nonlocal equations of motion of slender nanobeams on nano-foundations are formulated and size-dependent free vibration problems are addressed. An efficient numerical approach is adopted to solve the governing integro-differential elastodynamic problem and fundamental frequencies are detected for an emblematic structural scheme. The effect of the nonlocal foundation parameter on the structural response is investigated by performing parametric dynamic analyses. The work provides an advantageous approach for modeling and design of a wide range of nano-scaled beam-like components of nano devices.