Three critical frequencies independent of boundary conditions together with a critical length, which determine the vibration behaviors of a nonlocal Timoshenko beam, are identified. Unlike a local Timoshenko beam which has two frequency spectra, a nonlocal Timoshenko beam may have two frequency spectra or one frequency spectrum depending on the nonlocal effect. The eigenfrequencies of the higher modes of a nonlocal Timoshenko beam, irrespective of its boundary conditions, are shown to asymptotically approach one critical frequency, which is mainly determined by the nonlocal effect and beam material properties. This asymptotic behavior is proposed as a new and reliable way to determine the nonlocal effect. The nonlocal effect is also shown to determine whether a special vibration mode called thickness shear vibration can occur.