Stateless deterministic network address translation (NAT) within a service provider network is described. A plurality of customer premise equipment (CPEs) positioned within customer networks and a NAT device positioned within a service provider network operate as ingress and egress for tunnels having network packets of a first network transport protocol that encapsulate inner network packets of a second network transport protocol. The NAT device stores a mapping table that maps, for each of the CPEs, a public network address of the first transport protocol to a public network address and restricted port range of the second transport protocol. The NAT device outputs control messages to communicate the respective restricted port range to each of the CPEs, and the CPEs provide network address translation within the customer networks at the ingress of the tunnels based on the restricted port range received from the NAT device of the service provider network.