We present a new approach for K-anonymity protection in Location-Based Services (LBSs). Specifically, we depersonalize location information by ensuring that each location reported for LBSs is a cloaking area that contains K different footprints— historical locations of different mobile nodes. Therefore, the exact identity and location of the service requestor remain anonymous from LBS service providers. Existing techniques, on the other hand, compute the cloaking area using current locations of K neighboring hosts of the service requestor. Because of this difference, our approach significantly reduces the cloaking area, which in turn decreases query processing and communication overhead for returning query results to the requesting host. In addition, existing techniques also require frequent location updates from all nodes, regardless of whether or not these nodes are requesting LBSs. Most importantly, our approach is the first practical solution that provides K-anonymity trajectory protection needed to ensure anonymity when the mobile host requests LBSs continuously as it moves. Our solution depersonalizes a user's trajectory (a time-series of the user's locations) based on the historical trajectories of other users.