An improved client network address translation ("NAT") system is provided. A memory allocation scheme is 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, the allocation scheme enables a large pool of client NAT addresses and reclaim client NAT addresses as subpools are allocated and freed.