Web services utilize a standard communication infrastructure such as XML and SOAP to communicate through the Internet. Even though Web services are becoming more and more widespread as an emerging technology, it is hard to test Web services because they are distributed applications with numerous aspects of runtime behavior that are different from typical applications. This paper presents a new approach to testing Web services based on EFSM (Extended Finite State Machine). WSDL (Web Services Description Language) file alone does not provide dynamic behavior information. This problem can be overcome by augmenting it with a behavior specification of the service. Rather than domain partitioning or perturbation techniques, we choose EFSM because Web services have control flow as well as data flow like communication protocols. By appending this formal model of EFSM to standard WSDL, we can generate a set of test cases which has a better test coverage than other methods. Moreover, a procedure for deriving an EFSM model from WSDL specification is provided to help a service provider augment the EFSM model describing dynamic behaviors of the Web service. To show the efficacy of our approach, we applied our approach to Parlay-X Web services. In this way, we can test Web services with greater confidence in potential fault detection.