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 such as the VToA designator and the called party phone number, analyzing the information, designating an ATM address of a called party 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. The method also includes extracting information from the output ATM setup message such as the ATM address of the called party CPE, designating the ATM address of the called party CPE that was stored in the first instance of the second parameter of the output ATM setup message to be stored in the first parameter of a destination ATM setup message, and generating a destination ATM setup message that includes the ATM address of the called party CPE stored in the first parameter and the called party phone number value stored in the second parameter. An illustrative intelligent network for providing VToA and private address translation is also provided.