Voice over IP (VoIP) is an important service on the Internet, and privacy for VoIP calls will be increasingly important for many people. Providing this privacy, however, is challenging, as anonymity services can be slow and unpredictable. In this paper, we propose a method for extending onion-routing style anonymity protocols for supporting anonymous VoIP (aVoIP) traffic with reasonable performance. We report the results of extensive experimentation across 210 globally placed PlanetLab proxies which shows that paths for reasonable aVoIP quality would need to be selected carefully. Our design includes an algorithm for the measurement and selection of paths for reasonable aVoIP performance and an analysis of the potential for attackers to take advantage of this algorithm to improve existing attacks. We show that aVoIP could be developed in an onion routing system with reasonable performance guarantees and a modest increase in risk to its users as compared to the standard path selection algorithm.