Point of Interest (POI) recommender systems (RSs) play a primary role in improving Location-based Social Networks’ user experience. This paper studies the potential usefulness of serendipity in POI recommendations. We first introduce a new POI RS, called Discovery, that attempts to improve the accuracy-serendipity trade-off. The proposed RS aims to recommend POIs that provide a pleasant surprise, allowing users to discover new venues known as serendipitous POIs. We then look closely at how serendipity affects the quality of POI suggestions by contrasting the outcomes of Discovery with those of three cutting-edge non-serendipitous POI RSs. We use two real-world datasets—Foursquare and Flickr—along with a variety of metrics to test our ideas. These include (i) accuracy, which checks the precision, recall, and f-measure of Top-N recommendations; and (ii) beyond-accuracy, which checks the categorical and geographical diversity, explainability, and coverage in terms of POIs. The reported experimental observations show that serendipity boosts POI recommendation accuracy and favors geographically proximate and explainable POIs. However, standard POI baselines outperform Discovery in terms of categorical diversity and coverage.