Network applications need a method to seamlessly translate hostnames to network addresses. Because of the several peculiar characteristics of mobile ad hoc networks (MANETs) such as lack of fixed infrastructure, resource-constrained nodes and dynamic node mobility, the current Domain Name System (DNS) is not suitable for MANET deployment. Moreover, the existing name resolution solutions proposed for MANETs are either not sufficiently robust to cope efficiently with the dynamic nature of MANETs or are resource greedy. This paper proposes and evaluates the architecture of a new name resolution protocol called MANET Naming Service (MNS), which is robust and efficient. Further, it can be integrated with any stateful auto-configuration (autoconf) protocol. Because of the integration, MNS reuses the directory structure of autoconf protocol, which allows MNS to acquire the efficiency of the directory-based protocols without any additional complexity of directory maintenance. For the purposes of illustration, an example of MNS integration with a new stateful Dynamic Host Auto-configuration Protocol for MANETs (DHAPM) is shown. The performance of integrated MNS is compared with other well-known protocols through extensive simulations. The performance evaluation shows that the MNS system provides high name resolution success and low latency, while maintaining low communication overhead. Furthermore, MNS is robust, scalable and supports node heterogeneity.