Methods and systems are provided for efficient handover of a media session between heterogeneous IP networks. A mobile device with Internet access can operate a software program to communicate with a corresponding node. The corresponding node may access the Internet through either (i) a NAT router or (ii) a public IP address. The mobile device establishes a media session with a corresponding node via the transmission of a first media stream and receipt of a second media stream, and a media control channel can optionally be implemented. The mobile device can acquire Internet access through a second IP address, and packets routed between the second IP address and the Internet may traverse a NAT router. A software routine can determine that handover of the media session from the first IP address to the second IP address is preferred.