A system and method for performing address translation for packets entering or leaving a network. In some embodiments, a private network that may be fully or partially virtualized can use a stateless tunneling mechanism to communicate with external networks, such as the Internet, without using an external IP address for every host on the private network. For example, a packet forwarding device using a stateless Port Address Translation (PAT) implementation can route the packets subject to PAT by using forwarding rules rather than by storing connection-tracking state. Connection state information can be maintained at the hosts rather than at the packet forwarding device.