In the continuous location-based service (LBS) queries, the trajectory k-anonymity method that incorporates user’s moving trend is becoming popular because of its high quality of service (QoS). The existing works often apply user’s moving direction to represent the user’s moving trend. However, the query destinations of the users with closer moving directions are not necessarily closer. As a result, the users in a cloaked set may diverge with the proceeding of the continuous queries, leading to large cloaked areas as well as a reduction of QoS. Therefore, in this paper, a new concept named “location similarity of query destination (LS-QD)”, is proposed to reflect user’s global moving trend. By incorporating LS-QD, we develop a novel trajectory k-anonymity method for continuous LBS queries. Our system architecture utilizes a quadtree model with a pyramid structure to construct the user cloaked sets conveniently. Both theoretical analysis and simulation experiments are carried out to evaluate the robustness and security performance of our proposed method. Compared with other existing methods, our LS-QD based k-anonymity method can reduce the cloaking area and cloaking time while increasing the cloaking success ratio by about 40%–70%, which demonstrates its superiority in guaranteeing QoS for continuous LBS queries.