The new user problem is an important and challenging issue that Context-Aware Recommender Systems (CARSs) must deal with, especially in the early stage of their deployment. It occurs when a new user is added to the system and there is not enough information about the user’s preferences in order to compute appropriate recommendations. It is common to address this problem in the recommendation algorithm, by using demographic attributes such as age, gender, and occupation, which are easy to collect and are reasonably good predictors of the user preferences. However, as we show here, user’s personality provides even better information for generating context-aware recommendations for places of interest (POI), and it is still easy to assess with a simple questionnaire. In our study, using a rating data set collected by a mobile app called STS (South Tyrol Suggests), we have found that by considering the user personality the system can better rank the recommendations for the new users.