Internet telephony can be defined as real-time voice or multimedia communications over packet switched networks, including the Internet. The advent of third generation, wireless telecommunications networks will make it much more popular by adding the wireless dimension. Millions of end-users will access Internet telephony services using wireless devices. These end-users will be highly mobile and will change locations very frequently. A key requirement in this environment is universal access. It stipulates that end-users have access to their advanced services from anywhere and from any terminal. Mobile agents can aid in meeting it in an efficient manner. They can carry services and follow roaming end-users. The paper presents the design, the implementation, and the evaluation of a mobile agent-based advanced service architecture for wireless Internet telephony. When a mobile agent carries services, subscription becomes a critical issue. The agent needs to be updated when the end-user subscribes or unsubscribes to services. Our architecture tackles the issue by proposing and evaluating two schemes: agent swapping and on-the-fly updating. Although, wireless Internet telephony is our prime target, the architecture is, to a large extent, independent of the underlying network and therefore applicable to Internet Telephony in general.