A policy server correlates information from several messages associated with a client device to implement an identity-based network access policy. The policy server receives a first message from a network element connected to the client device. The first message requests an identity-based policy for the client device, and includes a first network address. The policy server receives a second message from an identity server. The second message includes information indicating an identity role and a second network address. The policy server receives a third message from a NAT device. The third message includes a NAT mapping that correlates the first network address with the second network address. After the policy server determines the identity-based policy based on a combination of the first message, the second message, and the third message, the policy server implements the identity-based policy in the network element.