This paper presents a new nonlocal stress variational principle approach for the transverse free vibration of an Euler-Bernoulli cantilever nanobeam with an initial axial tension at its free end. The effects of a nanoscale at molecular level unavailable in classical mechanics are investigated and discussed. A sixth-order partial differential governing equation for transverse free vibration is derived via variational principle with nonlocal elastic stress field theory. Analytical solutions for natural frequencies and transverse vibration modes are determined by applying a numerical analysis. Examples conclude that nonlocal stress effect tends to significantly increase stiffness and natural frequencies of a nanobeam. The relationship between natural frequency and nanoscale is also presented and its significance on stiffness enhancement with respect to the classical elasticity theory is discussed in detail. The effect of an initial axial tension, which also tends to enhance the nanobeam stiffness, is also concluded. The model and approach show potential extension to studies in carbon nanotube and the new result is useful for future comparison.