There are several deficiencies in the statistical approaches proposed in the literature for the assessment and redesign of surface water-quality-monitoring locations. These deficiencies vary from one approach to another, but generally include: (i) ignoring the attributes of the basin being monitored; (ii) handling multivariate water quality data sequentially rather than simultaneously; (iii) focusing mainly on locations to be discontinued; and (iv) ignoring the reconstitution of information at discontinued locations. In this paper, a methodology that overcomes these deficiencies is proposed. In the proposed methodology, the basin being monitored is divided into sub-basins, and a hybrid-cluster analysis is employed to identify groups of sub-basins with similar attributes. A stratified optimum sampling strategy is then employed to identify the optimum number of monitoring locations at each of the sub-basin groups. An aggregate information index is employed to identify the optimal combination of locations to be discontinued. The proposed approach is applied for the assessment and redesign of the Nile Delta drainage water quality monitoring locations in Egypt. Results indicate that the proposed methodology allows the identification of (i) the optimal combination of locations to be discontinued, (ii) the locations to be continuously measured and (iii) the sub-basins where monitoring locations should be added. To reconstitute information about the water quality variables at discontinued locations, regression, artificial neural network (ANN) and maintenance of variance extension (MOVE) techniques are employed. The MOVE record extension technique is shown to result in a better performance than regression or ANN for the estimation of information about water quality variables at discontinued locations.