While most prior studies in Location-Based Social Networks (LSBNs) have mainly centered around areas such as Point-of-Interest (POI) recommendation and place tag annotation, there exists no works looking at the problem of associating place-type to venues in LBSNs. Determining the type of places in location-based social networks may contribute to the success of various downstream tasks such as Point-of-Interest recommendation, location search, automatic place name database creation, and data cleaning. In this paper, we propose a multi-objective ensemble learning framework that (i) allows the accurate tagging of places into one of the three categories: public, private, or virtual, and (ii) identifying a set of solutions thus offering a wide range of possible applications. Based on the check-in records, we compute two types of place features from (i) specific patterns of individual places and (ii) latent relatedness among similar places. �e features extracted from specific patterns (SP) are derived from all check-ins at a specific place. The features from latent relatedness (LR) are computed by building a graph of related places where similar types of places are connected by virtual edges. We conduct an experimental study based on a dataset of over 2.7M check-in records collected by crawling Foursquare-tagged tweets from Twitter. Experimental results demonstrate the effectiveness of our approach to this new problem and show the strength of taking various methods into account in feature extraction. Moreover, we demonstrate how place type tagging can be beneficial for place name recommendation services.