Web services specification provides an open standard for the distributed service oriented architecture. It is widely used in Internet and pervasive networks supporting wireless mobile devices. A mobile agent is a composition of computer software and data which is able to migrate from one host to another autonomously and continue its execution on the destination host. Mobile agent technology can reduce the bandwidth requirement and tolerate the network faults - able to operate without an active connection between clients and server. Hence, the applications of the combination of mobile agents and web service have been widely investigated in recent years. However, the security issue is still of a major concern. In this paper, we propose a novel agent-based web service security scheme. This scheme provides a new authentication protocol without using the username/ password pair, which is infeasible for mobile agent, and gives an alternative method to current security mechanism without using Certification Authorities (CA) based public key infrastructure. With this scheme, we can simplify the key management and reduce the computation particularly for group-oriented web services.