A method for designing groundwater monitoring networks to define the extent of agricultural contamination is proposed. The method is particularly well suited to reducing existing networks where data are missing from time series records. A simulated annealing optimization algorithm is used to minimize the variance of the estimation error obtained by kriging in combinatorial problems, created by selecting an optimal subset of stations from the original set. Optimization is performed for several measuring times, obtaining an equal number of optimized small-dimension networks; stations that repeat more often in these networks are selected to make part of the final network. A compliance groundwater nitrate monitoring network in the south of Portugal is used to illustrate the method. The original 89-station network was converted into 16 stations. Results show that considerable reductions in operating costs (about 80%) are compatible with a cost-effective network capable of detecting noncompliance with national and European norms.