Estimation of pipe roughness coefficients is an important task to be carried out before any water distribution network model is used for online applications such as monitoring and control. In this study, a combined state and parameter estimation model for water distribution networks is presented. Typically, estimation of roughness coefficient for each individual pipe is not possible due to non-availability of sufficient number of measurements. In order to address this problem, a formal procedure based on K-means clustering algorithm is proposed for grouping the pipes which are likely to have the same roughness characteristics. Also, graph-theoretic concepts are used to reduce the dimensionality of the problem and thereby achieve significant computational efficiency. The performance of the proposed model is demonstrated on a realistic urban water distribution network. © 2009 Springer Science+Business Media B.V.