An address management scheme allows a Network Management System (NMS) to manage devices in a private network operating behind a Network Address Translator (NAT) boundary. A device operating in the private network sends a communication to a Simple Traversal of User Datagram Protocol (UDP) Through Network Address Translators (NATs) (STUN) server. The STUN server responds by communicating a public NAT IP address and a NAT port number back to the device. The device then provides the NMS with the public NAT IP address, a NAT port number associated with the device, a unique device identifier, and the private device IP address. The NMS stores this information in a table and then accesses this address information to manage the device in the private network. The device then uses the STUN server to identify any changes to the device address information and then sends the changes to the NMS.