An improved client network address translation ("NAT") system is provided. Methods are provided for initializing connection control blocks with the client NAT addresses when a storage pool of connection control blocks are allocated. This avoids the costly overhead as connections are created and destroyed. Unlike the prior art solutions, once the connection control blocks of the present invention are allocated, they remain in effect until the storage subpool is deleted. Secondly, in order to provide as large a pool of client NAT addresses as possible, methods are provided for using intervals to allocate and reclaim client NAT addresses as subpools are allocated and freed.