Mobility prediction algorithm is the significant aspect to improve QoS (Quality of Service) for heterogeneous wireless networks because it can accurately predict user’ s trajectory, decrease handoff latency and preserve resources in arriving cell for user. Considering inaccurate description of existing mobility prediction algorithms for mobile user’s location in heterogeneous wireless networks, this paper proposes that overlay coverage zone (OCZ) can be used to precisely describe user’s location, flexibly depict the mobile user’s characteristics and vertical handoffs among different wireless networks. As existing algorithms highly depend on cell boundary estimation and suffer from low time prediction accuracy, the phase-type distribution is introduced to model user’s residence time in OCZ to improve classical Markov predictor, and then a novel joint time and location mobility prediction algorithm is proposed. Simulation results show that, compared with Markov mobility prediction algorithm, the prediction accuracy of the proposed algorithm is highly increased.