Pd-catalyzed reduction has emerged as a promising treatment strategy to remove the recalcitrant disinfection byproduct N-nitrosodimethylamine (NDMA). However, the reaction pathways remain unexplored, and questions remain about how water solvent influences NDMA reduction mechanisms and selectivity. Here, we compute the energies and barriers of all relevant elementary steps in NDMA reduction by H2 on Pd(111) using density functional theory. We further calculate water-assisted H-shuttling for all hydrogenation reactions explicitly and include water solvation for all elementary reactions implicitly. We parametrize microkinetic models to predict product formation rates and selectivities over a wide range of NDMA concentrations. We show that H2O-mediated H-shuttling lowers the reaction barriers for all hydrogenation reactions involved in NDMA reduction while implicit solvation has negligible impact on the reaction and activation energies. We further conduct batch experiments with SiO2-supported Pd nanoparticles and compare them with the microkinetic models. The predicted rates, selectivity, and apparent activation energy from the model parametrized with both explicit H2O-mediated H-shuttling and implicit solvation correspond well with experimental observations. Models that ignore water as an H-shuttle or solvent fail to recover the experimental rates and apparent activation energy. We identified the rate-determining steps of the reaction and show the reaction flow pathways of the complicated reaction network. Finally, we demonstrate that water-mediated H-shuttling changes the rate-determining steps and reaction flows of elementary reactions.