This volume contains the papers presented at WS-FM 2007, the 4th International Workshop on Web Services and Formal Methods, held on September 28 and 29, 2007 in Brisbane, Australia. Web service technology aims at empowering providers of services, in the broad sense, with the ability to package and deliver their services by means of software applications available on the Web. Existing infrastructures for Web services - ready enable providers to describe services in terms of structure, access policy and behaviour, to locate services, to interact with them, and to bundle simpler services into more complex ones. However, innovations are needed to seamlessly extend this technology in order to deal with challenges such as managing int- actions with stateful and long-running Web services, managing large numbers of Web services each with multiple interfaces and versions, managing the quality of Web service delivery, etc. Formal methods have a fundamental role to play in shaping innovations in Web service technology. For instance, formal methods help to define and to understand the semantics of languages and prools that underpin existing infrastructures for Web services, and to formulate features that are found to be lacking. They also provide a basis for reasoning about Web service behaviour, for example to discover individual services that can fulfil a given goal, or even to compose multiple services that can collectively fulfil a goal. Finally, formal analysis of security properties and performance are relevant in many application areas of Web services such as e-commerce and e-business.