A distributed call routing system and method are used to provide higher quality VoIP connections with flexible codec choices and simplified NAT and firewall traversal. An analog telephone adapter (ATA) communicates a call destination to a network information server (NIS), which provides multiple routes. The ATA uses this information and local and/or non-NIS information to initiate the call using the preferred routing.