From the business perspective: A Web Service is a software asset that automates a task and can be shared, combined, used, and reused by different people or systems within or among organizations.
From the information systems perspective: A Web service is a software system designed to support interoperable machine-to-machine interaction over a network. It has an interface described in a machine-processable format (specifically WSDL). Other systems interact with the Web Service in a manner prescribed by its description using SOAP-messages, typically conveyed using HTTP with an XML serialization in conjunction with other Web-related standards. [From http://www.w3c.org.]