We theoretically study the Kondo screening of a spin-1/2 magnetic impurity in the bulk of a type-II Weyl semimetal (WSM) by use of the variational wave function method. We consider a type-II WSM model with two Weyl nodes located on the $k_z$-axis, and the tilting of the Weyl cones are along the $k_x$ direction. Due to co-existing electron and hole pockets, the density of states at the Fermi energy becomes finite, leading to a significant enhancement of Kondo effect. Consequently, the magnetic impurity and the conduction electrons always form a bound state, this behavior is distinct from that in the type-I WSMs, where the bound state is only formed when the hybridization exceeds a critical value. Meanwhile, the spin-orbit coupling and unique geometry of the Fermi surface lead to strongly anisotropic Kondo screening cloud in coordinate space. The tilting terms break the rotational symmetry of the type-II WSM about the $k_z$-axis, but the system remains invariant under a combined transformation $mathcal{T}R^{y}(pi)$, where $mathcal{T}$ is the time-reversal operation and $R^{y}(pi)$ is the rotation about the $y$-axis by $pi$. Largely modified diagonal and off-diagonal components of the spin-spin correlation function on three principal planes reflect this change in band symmetry. Most saliently, the tilting terms trigger the emergence of non-zero off-diagonal components of spin-spin correlation function on the $x$-$z$ principal plane.