In this paper, the small size effect on the free vibration behavior of finite length nanotubes embedded in an elastic medium is investigated. The problem is formulated based on the three-dimensional (3D) nonlocal elasticity theory. Since the 3D nonlocal constitutive relations in a cylindrical coordinate system are used, in addition to displacement components, the stress tensor components are chosen as degrees of freedom. The surrounding elastic medium is modeled as the Winkler’s elastic foundation. The differential quadrature method as an efficient and accurate numerical tool in conjunction with the series solution is used to discretize the governing equations. Very fast rate of convergence of the method is demonstrated. The effects of the nonlocal parameter together with the other geometrical parameters and also the stiffness parameter of the elastic medium on the natural frequencies are studied.