A monitoring network that resolves the spatial and temporal variations of the water quality is essential in the sustainable management of water resources and pollution control. Due to cost concerns, it is important to optimize the monitoring locations so to use the least number of stations required to obtain the most comprehensive monitoring. The optimal design of monitoring networks is commonly based on the limited data available from existing measuring stations. The main contribution of this paper is the use of a numerical water quality model, calibrated with the available data. This model yields information on the water quality in any cross-section along the river, including the river reaches that are not monitored. Another contribution of the paper is the use of a matter-element analysis that allows for an objective division of the river in reaches that are homogeneous with respect to the water quality as assessed from multiple water quality parameters. The optimal monitoring network consists of one measuring station in each of these homogeneous reaches. The method has been applied to optimize the water quality monitoring network on the 1890 km long upper and middle reaches of the Heilongjiang River in Northeast China. The results suggest that the monitoring network improves considerably by relocating three stations, and not by adding extra stations.