NAT (Network Address Translation) is a firewall or router function that operates by rewriting the IP addresses in the IP headers as packets pass from one interface to the other. When a packet, for example, is sent from the inside, the source IP address and port are rewritten from the private IP address space into the address space on the outside (Internet).
NAT rewrites the addresses but leaves the packets themselves untouched. This kind of translation works fine for many protocols, but causes a lot of trouble for SIP packets that contain address information in their content (for example an INVITE request from one IP address to another).
NAT traversal solves this problem, providing a “view from the outside” that makes it possible to replace the IP address in the SIP requests with the address shown on the other side of the firewall.
Note that in some cases NAT traversal is not necessary. Some public service providers of IP telephony keep track of the actual IP address used to register a phone, and the one used in the SIP requests from the same phone, and then replaces the addresses in the SIP messages.