Mobile WiMAX is a wireless networking system based on the IEEE 802.16e standard. In order to support mobile, some kinds of handover schemes must be adopted, and the hard handover is defined as mandatory. Since the data transmission should be paused during the hard handover process, it causes handover delay in mobile communication. The handover delay makes severe degradation in system performance when implemented in real-time applications such as IPTV and VoIP. The existing draft standard considers only the received signal strength when deciding handover initiation. However, the velocity factor also has an important influence on handover initiation and can not be neglected. To deal with these problems, this article proposes a velocity-adaptive handover scheme. This scheme adopts dynamic handover threshold according to different velocity to skip some unnecessary handover stages, reduces handover delay and enhances the network resource utilization. The simulation result and performance analysis validate the efficiency of the proposed scheme.