Stateful failover redundancy support is provided for network address translation (NAT). A master NAT device is backed-up with at least one back-up NAT device. Existing sessions are synchronized between the two NAT devices, such as via a dedicated link between them. In the event of a failover where the master NAT device is unable to perform its NAT functions, ownership of Internet protocol (IP) addresses is transferred from the master NAT device to the back-up NAT device. The back-up NAT device, which is now owner of the IP addresses, assumes the NAT functionality associated with these IP addresses and continues the existing sessions, as well as processing new sessions.