The wide spread of location-based services results in a strong market for location-detection devices (e.g., GPS-like devices, RFIDs, handheld devices, and cellular phones). Examples of location-based services include location-Aware emergency service, location-based advertisement, live traffic reports, and location-based store finder. However, location-detection devices pose a major privacy threat on its users where it transmits private information (i.e., the location) to the server who may be untrustworthy. The existing model of location-based applications trades service with privacy where if a user wants to keep her private location information, she has to turn off her location-detection device, i.e., unsubscribe from the service. This paper tackles this model in a way that protects the user privacy while keeping the functionality of location-based services. The main idea is to employ a trusted third party, the Location Anonymizer, that expands the user location into a spatial region such that: (1) The exact user location can lie anywhere in the spatial region, and (2) There are k other users within the expanded spatial region so that each user is k-Anonymous. The location-based database server is equipped with additional functionalities that support spatio-Temporal queries based on the spatial region received from the location anonymizer rather than the exact point location received from the user.