Nowadays, wireless packet data services are provided over Wireless MAN (WMAN) at a high data service rate, while 3G cellular networks provide wide-area coverage at a low data service rate. The integration of mobile WiMAX and 3G networks is essential, to serve users requiring both high-speed wireless access as well as wide-area connectivity. In this paper, we propose a cross-layer optimization scheme for a vertical handover between mobile WiMAX and 3G cellular networks. More specifically, L2 (layer 2) and L3 (layer 3) signaling messages for a vertical handover are analyzed and reordered/combined, to optimize the handover procedure. Extensive simulations using ns-2 demonstrate that the proposed scheme enhances the performance of a vertical handover between mobile WiMAX and 3G networks: low handover latency, high TCP throughput, and low UDP packet loss ratio.