We establish that massive complex Abelian vector fields (mass mu) can form gravitating solitons, when minimally coupled to Einstein's gravity. Such Proca stars(PSs) have a stationary, everywhere regular and asymptotically flat geometry. The Proca field, however, possesses a harmonic time dependence (frequency w), realizing Wheeler's concept of geons for an Abelian spin 1 field. We obtain PSs with both a spherically symmetric (static) and an axially symmetric (stationary) line element. The latter form a countable number of families labelled by an integer m epsilon Z(+). PSs, like (scalar) boson stars, carry a conserved Noether charge, and are akin to the latter in many ways. In particular, both types of stars exist for a limited range of frequencies and there is a maximal ADM mass, M-max, attained for an intermediate frequency. For spherically symmetric PSs (rotating PSs with m = 1, 2, 3), M-max similar or equal to 1.058M(PI)(2)/mu (M-max similar or equal to 1.568, 2.337, 3.247 M-PI(2)/mu), slightly larger values than those for (mini-)boson stars. We establish perturbative stability for a subset of solutions in the spherical case and anticipate a similar conclusion for fundamental modes in the rotating case. The discovery of PSs opens many avenues of research, reconsidering five decades of work on (scalar) boson stars, in particular as possible dark matter candidates. (C) 2015 The Authors. Published by Elsevier B.V.