Disclosed are, inter alia, methods, apparatus, computer-storage media, mechanisms, and means associated with load balancing across multiple network address translation (NAT) instances and/or processors. N network address translation (NAT) processors and/or instances are each assigned a portion of the source address traffic in order to load balance the network address translation among them. Additionally, the address space of translated addresses is partitioned and uniquely assigned to the NAT processors and/or instances such that the identification of the assigned NAT processor and/or instance associated with a received translated address can be readily determined there from, and then used to network address translate that received packet.