This paper studies strong delay-independent stability of linear time-invariant systems. It is known that delay-independent stability of time-delay systems is equivalent to some frequency-dependent linear matrix inequalities. To reduce or eliminate conservatism of stability criteria, the frequency domain is discretized into several sub-intervals, and piecewise constant Lyapunov matrices are employed to analyze the frequency-dependent stability condition. Applying the generalized Kalman-Yakubovich-Popov lemma, new necessary and sufficient criteria are then obtained for strong delay-independent stability of systems with a single delay. The effectiveness of the proposed method is illustrated by a numerical example. (C) 2016 Elsevier Ltd. All rights reserved.