Integrated WiMAX and WiFi networks is of great potential for the future due to the wider coverage of WiMAX and the high data transport capacity of WiFi. However, seamless and secure handover (HO) is one of the most challenging issues in this field. In this paper, we present a novel vertical HO authentication scheme with privacy preserving for WiMAX-WiFi heterogeneous networks. Our scheme uses ticket-based and pseudonym-based cryptographic methods to secure HO process and to achieve high efficiency. The formal verification by the AVISPA tool shows that the proposed scheme is secure against various malicious attacks and the simulation result indicates that it outperforms the existing schemes in terms of communication and computation cost.