This paper deals with the problem of delay-dependent robust stability for systems with time-varying structured uncertainties and time-varying delays. Some new delay-dependent stability criteria are devised by taking the relationship between the terms in the Leibniz-Newton formula into account. Since free weighting matrices are used to express this relationship and since appropriate ones are selected by means of linear matrix inequalities, the new criteria are less conservative than existing ones. Numerical examples suggest that the proposed criteria are effective and are an improvement over previous ones. (C) 2004 Elsevier Ltd. All rights reserved.