Decentralized Voice over IP networks are a promising alternative to classical server-based SIP networks especially in disaster areas or areas without centralized infrastructure. This paper presents P2PNS, a secure distributed name service for P2PSIP. P2PNS can be used to resolve SIP AoRs to Contact URIs without using DNS or centralized SIP servers. The name service provides several security mechanisms to efficiently prevent identity theft and to ensure the uniqueness of SIP AoRs in a completely decentralized and untrusted network. The proposed two-stage name resolution mechanism allows to efficiently handle frequent IP address changes. Because P2PNS provides a generic name service it is not limited to P2PSIP but can also be used e.g. to build a distributed DNS system.