A (3 + 1)-dimensional Einstein-Gauss-Bonnet effective description of gravity has been recently formulated as the D -> 4 limit of the higher dimensional field equations after the rescaling of the coupling constant. This approach has been recently extended to the four-dimensional Einstein- Lovelock gravity. Although validity of the regularization procedure has not been shown for the general case, but only for a wide class of metrics, the black-hole solution obtained as a result of such a regularization is also an exact solution in the well defined 4D Einstein-Gauss-Bonnet theory suggested by Aoki et al. (2005) and in the scalar-tensor effective classical theories. Here we study the eikonal gravitational instability of asymptotically flat, de Sitter and anti-de Sitter black holes in the four dimensional Einstein-Gauss-Bonnet and Einstein-Lovelock theories. We find parametric regions of the eikonal instability for various orders of the Lovelock gravity, values of coupling and cosmological constants, and share the code which allows one to construct the instability region for an arbitrary set of parameters. For the four-dimensional Gauss-Bonnet black holes we obtain the region of stability in analytic form. Unlike the higher dimensional Einstein-Lovelock case, the eikonal instability serves as an effective cut-off of higher curvature Lovelock terms for the 4D black holes.