Linear dynamics of Euler-Bernoulli beams with non-viscous non-local damping is considered. It is assumed that the damping force at a given point in the beam depends on the past history of velocities at different points via convolution integrals over exponentially decaying kernel functions. Conventional viscous and viscoelastic damping models can be obtained as special cases of this general damping model. The equation of motion of the beam with such a general damping model results in a linear partial integro-differential equation. Exact closed-form equations of the natural frequencies and mode-shapes of the beam are derived. Numerical examples are provided to illustrate the new results.