As use of location-based services (LBSs) is becoming increasingly prevalent, mobile users are more and more enticed to reveal their locations, which may be exploited by attackers to infer the points of interest (POIs) the users visit and then their privacy information. We propose a novel approach to the protection of a user's location privacy based on unobservability, preventing the attackers from relating any particular POI to the user's current location. We design, implement, and evaluate a privacy-protection system, called the Location Information ScrAmbler (LISA) which protects the user's location privacy by adjusting the location noise and hence, the uncertainty of associating his location with any POI, while conserving resources (especially battery energy) on mobile devices. By protecting location privacy locally on each mobile user's device, LISA eliminates the reliance on the trusted third-party servers required by most existing approaches. Therefore, it not only avoids the vulnerability of a single point of failure, but also facilitates the deployment of LBSs. Our evaluation of LISA using real-world users' traces demonstrates its efficacy and efficiency. © 2013 IEEE.