The communication paradigm has rapidly shifted from wireless mobile networks to All-Internet Protocol (IP) networks such as Multimedia Sub-system (IMS), Multi-Media Domain (MMD), and Worldwide Interoperability for Microwave Access (WiMAX), led by service industry leaders and communication manufacturers. This emerging communication paradigm is to provide new various services, such as ubiquitous multimedia services, with anyone, anytime, anyplace by using IP-based mobile devices. In this paradigm, providing authentication and session keys of a subscriber is a critical tasks because of the open accessibility and heterogeneousness of an All-IP network. In this paper, we develop a so-called Integrated Mobile Authentication Server (IMAS) that can securely inter-work among all mobile networks and fully support the legacy networks with backward compatibility. In designing IMAS, the mobile authentication inter-working mechanism and other issues to be overcome are addressed. A test environment for IMAS is established, and performance results are analyzed and evaluated. It is demonstrated that IMAS works in an All-IP network without compensating the efficiency and functionalities of the legacy networks.