As one of the promising branches of the Internet of Things, the cloud-enabled Internet of Vehicles (CE-IoV) is envisioned to serve as an essential data sensing, exchanging, and processing platform with powerful computing and storage capabilities for future intelligent transportation systems. The CE-IoV shows great promise for various emerging applications. In order to ensure uninterrupted and high-quality services, a vehicle should move with its own VM via live VM migration to obtain real-time location-based services. However, the live VM migration may lead to unprecedented location privacy challenges. In this article, we study location privacy issues and defenses in CE-IoV. We first present two kinds of unexplored VM mapping attacks, and thus design a VM identifier replacement scheme and a pseudonym-changing synchronization scheme to protect location privacy. We carry out simulations to evaluate the performance of the proposed schemes. Numerical results show that the proposed schemes are effective and efficient with high quality of privacy. © 2016 IEEE.