This article investigates the longitudinal vibration of a nanorod embedded in viscoelastic medium according to the nonlocal strain gradient theory. Viscoelastic medium is considered based on Kelvin-Voigt model. Governing partial differential equation is derived based on longitudinal equilibrium and analytical solution is obtained by adopting harmonic motion solution for the nanorod. Modal frequencies and corresponding damping ratios are presented to demonstrate the influences of nonlocal parameter, material length scale, elastic and damping parameters of the viscoelastic medium. It is observed that material length scale parameter is very influential on modal frequencies especially at lower values of nonlocal parameter whereas increase in length scale parameter has less effect at higher values of nonlocal parameter when the medium is purely elastic. Elastic stiffness and damping coefficient of the medium have considerable impacts on modal frequencies and damping ratios, and the highest impact of these parameters on frequency and damping ratio is seen in the first mode. Results calculated based on strain gradient theory are quite different from those calculated based on classical elasticity theory. Hence, nonlocal strain gradient theory including length scale parameter can be used to get more accurate estimations of frequency response of nanorods embedded in viscoelastic medium.