Techniques for implementing client compliancy in a network address translation (NAT) environment are disclosed. Network appliances (e.g., NAT hubs, routers, switches, and other NAT devices) actively cooperate with client compliance strategies by engaging in the compliance evaluation of the hosts connected to it, and interact with the up-stream compliance mechanism. As such, devices normally hidden behind a NAT device from the upstream network can participate in the compliance scheme in a more meaningful way.