With the proliferation of mobile devices and advances in positioning technologies, the location-based services (LBSs) have emerged as one of the killer applications for mobile users. Preserving user location privacy is one of the most crucial issues for LBSs. In this paper, we propose a new concept of k-anonymity to preserve users' location privacy. We devise a novel cloaking algorithm, called split cloaking, to generate a set of distributed cloaking regions. These distributed cloaking regions achieve higher k-anonymity for mobile users, leading to better privacy protection. In addition, the split cloaking algorithm addresses the problem that the number of querying users is too small to achieve k-anonymity. The experimental results show that the split cloaking algorithm is effective in user location privacy preservation.