A system, method and program product for provisioning a large scale network address translation (LSN) system. A system is disclosed that processes packets between a router and a TCP/IP network. The system includes a plurality of LSN appliances and a flow processor embedded in each of the plurality of LSN appliances. Each flow processor includes: a hash function that determines an owner appliance from the plurality of LSN appliances for a request received from the router based on a private IP address of the request; a look-up table that that determines the owner appliance from the plurality of LSN appliances for a response received from the TCP/IP network based on a public IP address of the response; and a packet routing system that routes a received request or a received response to the owner appliance.