In this study, free vibration analyses of embedded carbon and silica carbide nanotubes lying on an elastic matrix are performed based on Eringen's nonlocal elasticity theory. These nanotubes are modeled as nanobeam and nanorod. Elastic matrix is considered as Winkler-Pasternak elastic foundation and axial elastic media for beam and rod models, respectively. The vibration formulations of the beam and rod are derived by utilizing Hamilton's principle. The obtained equations of motions are solved by the method of separation of variables and finite element-based Hermite polynomials for various boundary conditions. The effects of boundary conditions, system modeling, structural sizes such as length, cross-sectional sizes, elastic matrix, mode number, and nonlocal parameters on the natural frequencies of these nanostructures are discussed in detail. Moreover, the availability of size-dependent finite element formulation is investigated in the vibration problem of nanobeams/rods resting on an elastic matrix.