Rotationally coherent Lagrangian vortices are formed by tubes of deforming fluid elements that complete equal bulk material rotation relative to the mean rotation of the deforming fluid volume. We show that the initial positions of such tubes coincide with tubular level surfaces of the Lagrangian-averaged vorticity deviation (LAVD), the trajectory integral of the normed difference of the vorticity from its spatial mean. The LAVD-based vortices are objective, i.e. remain unchanged under time-dependent rotations and translations of the coordinate frame. In the limit of vanishing Rossby numbers in geostrophic flows, cyclonic LAVD vortex centres are precisely the observed attractors for light particles. A similar result holds for heavy particles in anticyclonic LAVD vortices. We also establish a relationship between rotationally coherent Lagrangian vortices and their instantaneous Eulerian counterparts. The latter are formed by tubular surfaces of equal material rotation rate, objectively measured by the instantaneous vorticity deviation (IVD). We illustrate the use of the LAVD and the IVD to detect rotationally coherent Lagrangian and Eulerian vortices objectively in several two- and three-dimensional flows.