  Bekenstein proved that in Einstein's gravity minimally coupled to one (or
many) real, Abelian, Proca field, stationary black holes (BHs) cannot have
Proca hair. Dropping Bekenstein's assumption that matter inherits spacetime
symmetries, we show this model admits asymptotically flat, stationary,
axi-symmetric, regular on and outside an event horizon BHs with Proca hair, for
an even number of real (or an arbitrary number of complex) Proca fields. To
establish it, we start by showing that a test, complex Proca field can form
bound states, with real frequency, around Kerr BHs: stationary Proca clouds.
These states exist at the threshold of superradiance. It was conjectured in
arXiv:1403.2757, that the existence of such clouds at the linear level implies
the existence of a new family of BH solutions at the non-linear level. We
confirm this expectation and explicitly construct examples of such Kerr black
holes with Proca hair (KBHsPH). For a single complex Proca field, these BHs
form a countable number of families with three continuous parameters (ADM mass,
ADM angular momentum and Noether charge). They branch off from the Kerr
solutions that can support stationary Proca clouds and reduce to Proca stars
when the horizon size vanishes. We present the domain of existence of one
family of KBHsPH, as well as its phase space in terms of ADM quantities. Some
physical properties of the solutions are discussed; in particular, and in
contrast with Kerr BHs with scalar hair, some spacetime regions can be
counter-rotating with respect to the horizon. We further establish a
no-Proca-hair theorem for static, spherically symmetric BHs but allowing the
complex Proca field to have a harmonic time dependence, which shows BHs with
Proca hair in this model require rotation and have no static limit. KBHsPH are
also disconnected from Kerr-Newman BHs with a real, massless vector field.
