Accurate simulation of terrestrial water storage (TWS), the integrated volume of water in soil, groundwater, snow, surface water and vegetation per unit area, is challenging. TWS is a critical but often overlooked model diagnostic that can improve understanding of hydrological processes, water resource management, and climate change impacts assessment. Observations of TWS anomalies from the Gravity Recovery and Climate Experiment (GRACE) satellite and its follow-on (GRACE-FO) missions provide observational constraints on model-simulated TWS. The similarity between large spatial scales of GRACE TWS retrievals and global land models like the Community Land Model (CLM) facilitates comparison of model-simulated and observed TWS anomalies as a function of input parameter values. We demonstrate an approach to optimize CLM parameters for improved TWS simulation, using history matching with Evidential Deep Neural Networks (EDNN). History matching is a constraining technique that identifies plausible parameter sets by comparing model outputs to observations. To reduce the computational expense of generating large perturbed parameter ensembles (PPEs) we use an emulator EDNN that provides a probabilistic framework for representing uncertainty in the relationship between input parameters and TWS. A key advantage of the EDNN approach is estimation of both epistemic and aleatoric uncertainty with the use of a single model, reducing the need to sample or train multiple ensembles. We applied the proposed methodology that utilizes history matching with EDNN to a real-world case study in which we compared CLM simulations to observed TWS data (e.g., from the GRACE satellite mission) over the Contiguous United States (CONUS). The optimization process focuses on key parameters (e.g., dry surface layer, decay factor for fractional saturated area, and medlyn slope of conductance-photosynthesis relationship) within the CLM that govern water storage dynamics. The resulting parameter sets yield model simulations of TWS that agree with observations. Moreover, uncertainty estimates could improve TWS simulations, enabling more robust assessments of global water availability and hydrological changes.