Web services (WSs) are used more and more as com- ponents of distributed applications with a goal to resolve complex tasks that simple services cannot. This use of WSs is connected to the emergence of languages like WS-BPEL which allows describing the external behaviour of WSs on top of the service interfaces. The use of WSs as components of distributed applications implies the possibility to change a failing service for another which can do at least the same thinks as the replaced service. Different solutions have been proposed during the last years to check such properties, but, to our knowledge, none of them take QoS aspects into ac- count. This paper introduces a set of tools and techniques for verifying WSs substitutivity while taking into account service costs such as the execution time of the different op- erations provided by WSs.