Distributed multi-agent systems require naming services to locate and communicate with remote agents. In this paper we focus on the design and implementation of the "White Pages," which maps names to addresses. We present an agent-based white pages architecture that is integrated with the communication and security mechanisms of the underlying agent framework, thereby inheriting all of their customized properties. The design is scalable, robust to failure and loss of persisted data, and supports mobile agents. Using the open source Cougaar agent architecture as our base example, we present experimental results for an agent society of 1300 agents running on 60 hosts.