Method and apparatus for establishing direct IP bi-directional or unidirectional connectivity between communication devices (6,24), accommodating the circumstance of either or both communication devices residing behind a Network Address Translator (NAT). When a communication device requests IP connectivity to another communication device, either the local or remote communication device's associated service node (26,28) or their agents (41,42) (or another node 29, using information collected by the devices' associated service nodes), formulates an appropriate direct IP pathway (40) to traverse any pertinent NATs and instructs the applicable communication devices (30,32,34,44,45,46,47) to self-configure to establish the pathway (40).