This paper is devoted to the first systematic investigation of manifolds that are Einstein for a connection with skew symmetric torsion. We derive the Einstein equation from a variational principle and prove that, for parallel torsion, any Einstein manifold with skew torsion has constant scalar curvature; and if it is complete of positive scalar curvature, it is necessarily compact and it has finite first fundamental group. The longest part of the paper is devoted to the systematic construction of large families of examples. We discuss when a Riemannian Einstein manifold can be Einstein with skew torsion. We give examples of almost Hermitian, almost metric contact, and G2 manifolds that are Einstein with skew torsion. For example, we prove that any Einstein-Sasaki manifold and any 7-dimensional 3-Sasakian manifolds admit deformations into an Einstein metric with parallel skew torsion.

24 pages, 1 figure, new version with erratum added at the end