Recent progress in the field of web services has made it possible to integrate inter-organizational and heterogeneous services on the web at runtime. If a user request cannot be satisfied by a single web service, it is (or should be) possible to combine existing services in order to fulfill the request. However, there are several challenging issues that need to be addressed before this can be realized in the true sense. One of them is the ability to ensure end-to-end QoS of a web service composition. There is a need for a SLA negotiation system which can ensure the autonomous QoS negotiation of web service compositions irrespective of the application domain. In this paper we propose agent-based coordinated-negotiation architecture to ensure collective functionality, end-to-end QoS and the stateful coordination of complex services. We describe a prototype implementation to demonstrate how this architecture can be used in different application domains. We have also demonstrated how the negotiation system on the service provider?s side can be implemented both as an Agent based Negotiation System and as a Web Service based Negotiation System.