To deal with stochastic multi-criterion decision-making problems, a new PROMETHEE Ⅱ method is developed. Based on expected utility theory, the method combines stochastic dominance relation and current PROMETHEE Ⅱ method. With the help of two kinds of thresholds, the different preference levels of the decision-makers are considered. According to the value of preference function for each pair of alternatives with respect to criterions, the multi-criterion outranking degree for each pair of alternatives is obtained and the leaving flow, the entering flow and the net flow for each alternative are worked out. Then, the ranking of alternatives is obtained. Finally, an example is given to show the feasibility and availability of the method.