At present, most destination prediction methods that combine spatial embedding and neural networks faced the trade-off between prediction accuracy and time performance, as well as the long-term dependence problem. Therefore, a hierarchical spatial embedding bidirectional gate recurrent unit (HSE-BiGRU) model for destination prediction was proposed. The proposed HSE-BiGRU model adopted a hierarchical architecture consisting of two stages. In the first stage, a coarse-grained grid embedding technique was employed to convert the GPS trajectory data into a grid embedding sequence. An attention-equipped BiGRU network was used to capture the spatiotemporal dependencies within the sequence and predict the destination’s grid region. In the second stage, a quadtree embedding technique was utilized to transform the trajectory data within the predicted grid region into a quadtree embedding sequence. Subsequently, the attention-equipped BiGRU network was applied to focus on critical location nodes within the quadtree embedding sequence, thereby extracting its motion characteristics. Finally, the destination was accurately predicted by integrating the features extracted from both stages. The performance of the proposed method was evaluated on the taxi dataset in Porto, and the experimental results showed that the proposed method was superior to the baseline models, for example CNN, T-CONV, and CNN-LSTM, in terms of prediction accuracy and time performance.