A novel 3-step solution concept based on fuzzy cooperative games was developed aimed at optimizing the water resources reallocation in water-stressed regions. In the first step, the characteristic function of the crisp water-sharing coalitions among water using sectors was constituted based on the “priority rule”, which dedicated to the reasonable illustration of the water resource sharing mode in each crisp coalition. In the second step, based on the fuzzy cooperative games in the form of Choquet integrals, and the characteristic function of crisp coalition constituted in Step 1, the characteristic function of fuzzy water resource sharing coalitions among water using sectors was established. In the third step, based on the results above, the optimal water resource reallocation model was proposed, and optimum fuzzy coalitions were obtained by solving this model. Furthermore, in this step, each optimum coalition was considered as a grand coalition, and the benefit of each grand coalition was distributed to water using sectors in a rational way by using the nucleolus method. This methodology was examined by applying it to a case study of water resource reallocation in the “Beijing-Tianjin-Hebei Region”. The results show that the proposed 3-step optimal water resource allocation model can ensure the maximum effect of water utilization, and can realize optimal water resource allocation. Moreover, the proposed model does not need to have the constrain of fuzzy Shapley value equation, if the model was constructed based on the fuzzy cooperative games in the form of Choquet integrals, that is, the optimal allocation model without affecting the validity of the distribution results obtained by using different distribution methods. Furthermore, the nucleolus solution of each optimum coalition uniquely exists, which can guarantee the stability of each optimum coalition by satisfying both individual rationality and group rationality criterions, which means that the proposed method based on nucleolus is more effective than the exiting method (Shapley value, fuzzy least core, and fuzzy weak least core) in the issue discussed in this paper.