With the prosperity of mobile internet and the pervasiveness of location-aware mobile terminals, online ridehailing, a high-level location-based service (LBS) which relies on dynamic location detection, has made our life more convenient. However, the flourish of ride-hailing service still faces many severe challenges since users’ location privacy and service provider’s data security. In this paper, we present an efficient and privacy-preserving dynamic location detection scheme (TRACE) for ride-hailing service. With TRACE, users (i.e., consumers and vehicles) can access ride-hailing service without divulging their sensitive location information, meanwhile, the ride-hailing server can achieve the necessary commercial operating information while keeping its sensitive data (i.e., the space division information) confidential. Specifically, with two proposed algorithms based on chipertext of fast range search, named FSSD and ECRS, all location-related data are encrypted by its owner before sending out, and are calculated without decryption during the location detection process. Therefore, consumers, vehicles, and service provider cannot obtain each other’s sensitive information. Detailed security analysis shows that TRACE can resist various known security threats. Furthermore, TRACE is implemented in the real environment, and extensive simulation results over smart phones demonstrate that the scheme is highly efficient and can be implemented effectively.