A mechanism for dynamically performing Network Address Translation that allows external devices to contact internal host systems that would otherwise be hidden behind a NAT device is discussed. The dynamic NAT mechanism of the present invention maps internal host system addresses to external network addresses and reconfigures the NAT configuration of the network firewall to account for the new mapping on demand. Domain Name Service (DNS) lookup requests for an authorized internal system serve as a trigger to create a new mapping between the internal host system and the external network address. The new mappings may have a lifecycle controlled by dynamic leases that are created for each new mapping.