This disclosure describes techniques for providing a distributed scalable architecture for Network Address Translation (NAT) systems with high availability and mitigations for flow breakage during failover events. The NAT servers may include functionality to serve as fast-path servers and/or slow-path servers. A fast-path server may include a NAT worker that includes a cache of NAT mappings to perform stateful network address translation and to forward packets with minimal latency. A slow-path server may include a mapping server that creates new NAT mappings, depreciates old ones, and answers NAT worker state requests. The NAT system may use virtual mapping servers (VMSs) running on primary physical servers with state duplicated VMSs on different physical failover servers. Additionally, the NAT servers may implement failover solutions for dynamically allocated routeable address/port pairs assigned to new sessions by assigning new outbound address/port pairs when a session starts and broadcasting pairing information.