The Web service selection phase is usually driven only by functional requirements. Non functional requirements, such as quality of service, should be negotiated by the service consumer and the service provider during service invocation in order to produce a contract to manage service provisioning and to monitor the actual fulfilment of negotiated SLAs. In this paper, an automated approach to Web service QoS negotiation is proposed; the negotiation is performed by a negotiation broker to which both the consumer and the service provider can notify their preferences on QoS attributes and negotiation strategies by specifying the value of a relatively small set of parameters. When consumers are unable to specify such parameters or do not trust the service provisioning platform, negotiation can also be automated only on the provider side, allowing the direct interaction of the service consumer with the broker. An architecture to support the above mentioned functionalities is also described.