Recent studies have demonstrated that incorporating delay-variation-dependent information can significantly reduce conservatism of stability criteria for discrete-time delayed systems. In this context, based on the discrete Bessel–Legendre inequality, a general free-matrix-based inequality is developed. This inequality improves the traditional estimation by fully utilizing the delay-variation-dependent information. Furthermore, by constructing a new delay-product-type Lyapunov functional and applying the improved inequality, novel stability criteria are consequently derived for discrete-time systems with a time-varying delay. The superiority of the proposed criteria in reducing conservatism is clearly illustrated through numerical examples.