An illustrative intelligent network and method for providing voice telephony over Asynchronous Transfer Mode (“ATM”) and private address translation are provided that can provide significant advantages. The method includes generating an input ATM setup message at the calling party CPE that includes a VToA designator and a called party phone number, extracting information from the input ATM setup message, analyzing the information, designating an ATM address of a called pany CPE to be stored in the first parameter of an output ATM setup message, determining if private address translation is needed, designating the ATM address of the called party CPE to be stored in a first instance of the second parameter of the output ATM setup message, designating an ATM address of an egress ATM edge switch to be stored in the first parameter of the output ATM setup message, and generating an output ATM setup message.