After adopting the constitutive equations of the nonlocal elastic media in the form of Eringen, and making use of the Laplace transformation, the vibration governing equation of nonlocal elastic beam in the Kelvin media are established. Unlike classical elastic models, the stress of a point in a nonlocal model is obtained as a weighted average of the field over the spatial domain, determined by a kernel function based on distance measures. The motion equation of nonlocal elastic beam is an integral differential equation, rather than the differential equation obtained with a classical local model. Solutions for natural frequencies and modes are obtained. Numerical examples demonstrate the efficiency of the proposed method for the beam with simple boundary conditions.