Service-oriented applications are typically built out of existing web-services (WSs) possibly made available by third party vendors. This requires that the application has to be able to evolve when the composing WSs are not anymore available or when new, more useful ones, are published. In this setting, an important problem is to understand how to use WSs showing an interface that differs from the one the application has been built to. The problem becomes even more complex when we consider conversational WSs, i.e., WSs that expose operations that have Input/Output (I/O) data dependencies among them. This paper presents a complete development methodology to the automatic synthesis of adapters for conversational WSs starting from their WSDL interface. The result is a tool-supported methodology that takes as input the WSDL of a pair of services and automatically builds a script that maps a sequence of operation invocations on a “WS to be replaced” into an equivalent sequence of operation invocations on the “replacing WS”. The overall approach is presented by applying it to two existing WSs that realize two distinct, but equivalent, search engines for lyric music.