The W3C defines a web service as:
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 Web Services Description Language, known by the acronym 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 (http://en.wikipedia.org/wiki/Web_service#cite_note-0).
This is a good starting point, which allows us to extract some ideas, to elaborate on them further:
Machine-to-machine communication
Described in WSDL
HTTP (or HTTPS) with an XML serialization (or at least formatted in XML, as data could be binary serialized)
What we call web services have in common that they are HTTP-based, so we can see them as an evolution of RPC, sockets, CORBA, and the like, being migrated to the Internet era with a brand new architecture...