Food, energy, and water (FEW) are interconnected pillars that underpin the security of people’s livelihoods. In this paper, we propose a decision-support model to better understand and aid management of regional FEW nexus systems under uncertainty. We apply the model to a case study focusing on fluctuations in water supply, which significantly affect production in the agriculture and energy sectors in Shanxi Province, China. We use a two-stage, stochastic, chance-constrained programming approach to the proposed spatially detailed cost-minimizing FEW nexus model under demand and natural resource (land and water) constraints. This approach translates the target reliability level (i.e., the probability that the devised solution can satisfy all constraints) into a penalty that has to be paid in the case of their non-fulfillment. On this basis, robust decisions (i.e., production options suitable for a broad variation in certainty of water supply) are derived. Using this approach, we estimate the penalties required to achieve given levels of reliability by incentivizing the deployment of water-saving technologies. For example, our model predicts that water storage would become cost-effective if the penalty for exceeding the available water supply were 2.5 times higher than the current price for industrial water; this would enable at least 40% reliability compared to 18% if the penalty were at the current water price level. Taking advantage of the differences in water intensity of crops in different sites, our model optimizes the reservoir location, which allows water withdrawal by agriculture to be reduced by 1.23%. We also evaluate the benefits of incorporating uncertainty and missed opportunity due to a lack of perfect information. In the case study, we show that the benefits of including uncertainty in the form of the two-stage stochastic programming approach appear to be quite significant, reaching 4% of the total solution costs. Water-importing costs, taxes, and subsidies are instruments that translate into the penalty in this model; the modeling approach presented here can thus be used to inform cost-effective and robust management of the FEW nexus in Shanxi Province, China, and other water-scarce regions around the world.