The World Wide Web Consortium defines a Web Service as "a software system designed to support interoperable machine-to-machine interaction over a network." Web Services have become increasingly important both within and across organizational boundaries. With the recent advent of the Semantic Web, web services have evolved into semantic web services whose components are described using machine understandable semantics. However, the discovery of semantic web services, the matching of user requirements to available services, still has a number of unanswered questions. In particular, there is criticism that current discovery methods focus exclusively on service inputs and outputs and ignore how services actually perform their tasks. This lack of information regarding how a service operates can also severely impact understanding of web service results. We show how ideas from data provenance-capturing the history and lineage of data--can be applied to web services. We describe our approach to capture service provenance using Semantic Web technologies and subsequently design a new web service discovery algorithm around it. Further, we present a framework for capturing and integrating provenance in multi-service workflows. [The dissertation citations contained here are published with the permission of ProQuest LLC. Further reproduction is prohibited without permission. Copies of dissertations may be obtained by Telephone (800) 1-800-521-0600. Web page: http://www.proquest.com/en-US/products/dissertations/individuals.shtml.]