Recent years have witnessed a rapid explosion of online information sources about restaurants, and the selection of an appropriate restaurant has become a tedious and time-consuming task. A number of online platforms allow users to share their experiences by rating restaurants based on more than one criterion, such as food, service, and value. For online users who do not have enough information about suitable restaurants, ratings can be decisive factors when choosing a restaurant. Thus, personalized systems such as recommender systems are needed to infer the preferences of each user and then satisfy those preferences. Specifically, multi-criteria recommender systems can utilize the multi-criteria ratings of users to learn their preferences and suggest the most suitable restaurants for them to explore. Accordingly, this paper proposes an effective multi-criteria recommender algorithm for personalized restaurant recommendations. The proposed Hybrid User-Item based Multi-Criteria Collaborative Filtering algorithm exploits users’ and items’ implicit similarities to eliminate the sparseness of rating information. The experimental results based on three real-word datasets demonstrated the validity of the proposed algorithm concerning prediction accuracy, ranking performance, and prediction coverage, specifically, when dealing with extremely sparse datasets, in relation to other baseline CF-based recommendation algorithms.