In this paper, a vertical handover algorithm based on motion trend prediction is proposed for the problem that the speed of vehicle in the heterogeneous IoV (Internet of Vehicles) is fast, which leads to the high switching failure rate and “ping-pong effect”. In the heterogeneous IoV environment composed of LTE and WiMAX, the duration of the current base station coverage is calculated by predicting the movement trend of the vehicle. According to the time, the vehicle node is divided into narrow mobile node and wide mobile node. For narrow mobile nodes, the network selection method based on load balancing is adopted to decide the handoff. For the mobile nodes, handoff decisions are carried out by using the multiple attribute vertical handoff algorithm based on Fuzzy Analytic Hierarchy Process (AHP). The simulation results show that the algorithm can reduce the number of handover, improve the switching delay and improve the throughput of the system in two kinds of simulation scenarios with different vehicle quantity and different vehicle speed.