Location-based services (LBSS) are widely used with the rapid development of mobile devices and location technology. LBSs not only brings convenience to life, but also brings privacy threats to users. Users upload accurate location information to LBSs to obtain the corresponding services. However, uploading unprocessed location data will directly cause the leakage of users’ privacy information. In this work, an efficient location protection method based on differential privacy is proposed. First of all, the users’ locations information is merged based on the distance and density relationship between multiple groups of continuous locations, and a location clustering (L-cluster) algorithm is proposed to divide the continuous locations into various clusters. Then, differential privacy based location protection algorithm (DPLPA) is proposed to efficiently preserve users’ location privacy, where Laplace noise conforming to the differential privacy mechanism is added to resident points and centroids in the cluster to protect the location privacy. Experimental results show that DPLPA gets high data utility and low time consumption while protecting the privacy of location information.