The design of an efficient handover technique is considered as one of the crucial topics in the cellular-based wireless networks. Feasible handover process can minimize the performance degradation as the mobile device is moving between different base stations. Based on the IEEE 802.16e standard, it is required to provide satisfactory handover performance under a wide-range of moving speeds of the mobile device. In this paper, a predictive movement-based handover (PMHO) algorithm is proposed. Without incurring excessive overheads as from the conventional location estimation and tracking techniques, the proposed sideline-traveling scheme within the PMHO algorithm employs the moving state indicator (MSI) to predict the potential moving characteristics of the mobile device. The handover decision of the PMHO approach is determined based on the MSI values associated with the neighbor base stations. Numerical results show that the proposed PMHO algorithm can effectively reduce both the number of handover and the size of the neighborscanning set within the mobile device.