In order to meet service users' personalized requirements, a latent semantic probabilistic model is proposed to predict users' criteria preferences for Web service recommendation. Users' criteria preferences are mainly affected by two key elements, users and their service situations. Firstly, the latent semantic relations among users, their criteria preferences and service situations are established with latent classes in this model. In order to describe multifaceted characteristics of users, service situations and users' criteria preferences, all of them are allowed to simultaneously belong to multiple latent classes with different probabilities. Afterwards, the expectation maximization algorithm and the consistent training data obtained by analytic hierarchy process are used to estimate the parameters of the latent semantic probabilistic model which contains latent variables. Finally, the trained model is employed to predict users' criteria preferences under specific service situations if users are unwilling to provide their criteria preferences due to lack of domain knowledge. The main advantage of the proposed latent semantic probabilistic model over the standard memory-based collaborative filtering and the collaborative filtering improved by clustering is an explicit and compact model representation. And the experimental results show that the algorithm based on the latent semantic probabilistic model can get higher prediction accuracy than both the standard and the improved collaborative filtering algorithms and can also alleviate the impact of data sparsity.