Data-driven Sparse Sensing (DSS) is an efficient sampling approach for reliable estimation of high-frequency time-series from a substantially lower number of samples. This study applies the DSS technique to estimate stream nutrient concentrations and loads (nitrate-nitrite as NOx and phosphorous as P) using sparse measurements of the nutrient concentrations and related surrogate variables such as discharge, temperature, conductance, turbidity, and dissolved oxygen. Using 61 stream datasets from the Midwestern U.S., we demonstrate that annual loads and daily nutrient concentration time-series can be accurately reconstructed using 18-73 discharge and concentration samples per year. The DSS technique also identifies optimal sampling times and locations. Optimal sampling times are generally distributed in the Spring (March-May). Optimal sampling locations for these surrogate measurements are either co-located with or in close proximity to, the nutrient monitoring gauge of interest. It is possible to predict nutrient concentrations and loads using sparse measurements (18–73 samples per year) conducted at optimal sampling times and locations maintaining a mean NSE value greater than 0.85 for NOx gauges and greater than 0.67 for P. Additionally, the annual NOx and P loads can be estimated with errors of less than ±1% and ±8% error respectively. As measurements of nutrients in rivers are vital for assessing water quality, identifying pollution sources, and preserving the health of river ecosystems, DSS has the potential to improve the efficiency and information capture of environmental monitoring schemes.