In this study, a two-stage interval-stochastic water trading (TIWT) model is developed for reallocating water resources under uncertainty, which integrates techniques of interval-parameter programing and two-stage stochastic programing into a general framework. The TIWT model can provide an effective linkage between system benefit and the associated economic penalty attributed to the violation of the pre-regulated water permit under uncertainties expressed as probabilistic distributions and interval values. The trading scheme is introduced to optimize water allocation of Kaidu-Kongque River in northwestern China. Results obtained suggest that trading program can effectively allocate limited water resources to competitive users by market approach in such an arid area, which improves economic efficiency in the mass (e.g., maximizing system benefits) and remedies water deficiency. A number of policies for water permits are analyzed and reveal that different water permits lead to different water shortages, system benefits, and system-failure risks. Tradeoffs between economic benefit and system-failure risk are also examined under different policies, which support generating an increased robustness in risk control for water resources allocation under uncertainty. The results are helpful for local decision-makers in adjusting the current water allocation pattern optimally.