The invention discloses a method and system for realizing NAT traversal, which relate to the communication technology field. The method comprises the following steps. A first terminal receives the signaling information sent from a second terminal wherein the signaling information carries the local address of the second terminal, the outgoing address of the NAT device at the second terminal, the forwarding address assigned by the proxy server of the second terminal, and the priorities of these three addresses. The first terminal sends a media message to the forwarding address assigned by the proxy server of the second terminal so as to establish a communication connection with the second terminal. The first terminal performs a connectivity test on the local address of the second terminal and the outgoing address of the NAT device. According to the priorities of the three addresses and the connectivity rest result, the first terminal determines whether to switch from sending the media message to the forwarding address assigned by the proxy server of the second terminal to sending the media message to the local address of the second terminal or the outgoing address of the NAT device or not. With the invention, it is possible to realize efficient traversal of various NAT devices for communication connections; and in addition, the continuous delay time is small; and the resources of the proxy server can be saved and the cost is reduced.