In the last few years, there has been a good deal of effort put into the research and standardization of P2P-based VoIP signaling, commonly called P2PSIP. However, there has been one important issue which has not been dealt with adequately, privacy. Specifically i) location privacy, and ii) privacy of social interaction in terms of who is communicating with whom. In this paper, we present Pr2-P2PSIP , a Privacy-Preserving P2PSIP signaling protocol for VoIP and IM. Our contribution is primarily a feasibility study tackling the privacy issues inherent in P2PSIP. We leverage standard security protocols as well as concepts and experiences learned from other anonymization networks such as Tor and I2P where applicable. We present the design and on-going implementation of Pr2-P2PSIP and provide a threat analysis as well as an analysis of the overhead of adding privacy to P2PSIP networks. Particularly we analyze cryptographic overhead, signaling latency and reliability costs.