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