Since the irruption of Web Services, in their SOAP and REST flavors, the market has turned from intra-business applications to inter-organizational applications. Nowadays, more organizations have a broad access to the Web and span their frontiers using service-centered applications. In this paper, we review the testing challenges and strategies in Web Services – as the technological weapon-of-choice to implement Business Services. Then we deepen into a possible strategy to address service testing: Test Reduction. Fresh strategies are necessary since Web Services testing is substantially different from legacy systems testing.