Vibration of nanotubes embedded in an elastic matrix is investigated by using the nonlocal Timoshenko beam model. Both a stress gradient and a strain gradient approach are considered. The Hamilton’s principle is adopted to obtain the frequencies of the nanotubes. The dependencies of frequency on the stiffness and mass density of the surrounding elastic matrix, the nonlocal parameter, the transverse shear stiffness and the rotary inertia of the nanotubes are obtained. The results show a significant dependence of frequencies on the surrounding medium and the nonlocal parameter. The frequencies are over-predicted by using the Euler beam model that neglects the shear stiffness and rotary inertia of the nanotubes. It is also found that the lower bound and the upper bound for the frequencies of nanotubes are, respectively, provided by the strain gradient model provides and the stress gradient theory. Explicit formulas for the frequency are obtained and therefore are easy to use by material scientists and engineers for the design of nanotubes and nanotubes based composites.