In this work, we present, for the first time, a numerical study of the Bondi-Hoyle accretion with density gradients in the fully relativistic regime. In this context, we consider accretion onto a Kerr Black Hole (BH) of a supersonic ideal gas, which has density gradients perpendicular to the relative motion. The set of parameters of interest in this study are the Mach number, M, the spin of the BH, a, and the density-gradient parameter of the gas, {\rho} . We show that, unlike in the Newtonian case, all the studied cases, especially those with density gradient, approach a stationary flow pattern. To illustrate that the system reaches steady state we calculate the mass and angular momentum accretion rates on a spherical surface located almost at the event horizon. In the particular case of M = 1, {\rho} = 0.5 and BH spin a = 0.5, we observe a disk-like configuration surrounding the BH. Finally, we present the gas morphology and some of its properties.