We model, for the first time, the Bondi-Hoyle accretion of a fluid with velocity gradients onto a Kerr black hole, by numerically solving the fully relativistic hydrodynamics equations. Specifically, we consider a supersonic ideal gas, which has velocity gradients perpendicular to the relative motion. We measure the mass and specific angular accretion rates to illustrate whether the fluid presents unstable patterns or not. The initial parameters, we consider in this work, are the velocity gradient $\epsilon_{v}$, the black hole spin $a$, the asymptotic Mach number ${\cal M}_{\infty}$ and adiabatic index $\Gamma$. We show that the flow accretion reaches a fairly stationary regime, unlike in the Newtonian case, where significant fluctuations of the mass and angular momentum accretion rates are found. On the other hand, we consider a special case where both density and velocity gradients of the fluid are taken into account. The spin of the black hole and the asymptotic Newtonian Mach number, for this case, are $a=0.98$ and ${\cal M}_{\infty}=1$, respectively. A kind of flip-flop behavior is found at the early times; nevertheless, the system also reaches a steady state.