Multiple attribute decision making (MADM) problem is one of the most common and popular research fields in the theory of decision science. A variety of methods have been proposed to deal with such problems. Nevertheless, many of them assumed that attribute weights are determined by different types of additional preference information which will result in subjective decision making. In order to solve such problems, in this paper, we propose a novel MADM approach based on cross-evaluation with uncertain parameters. Specifically, the proposed approach assumes that all attribute weights are uncertain. It can overcome the drawback in prior research that the alternatives’ ranking may be determined by a single attribute with an overestimated weight. In addition, the proposed method can also balance the mean and deviation of each alternative’s cross-evaluation score to guarantee the stability of evaluation. Then, this method is extended to a more generalized situation where the attribute values are also uncertain. Finally, we illustrate the applicability of the proposed method by revisiting two reported studies and by a case study on the selection of community service companies in the city of Hefei in China.