Web services are a popular choice for component oriented systems. Web services not only provide a platform independent architecture but also support dynamic compositions to facilitate on the fly creation of composite solutions. Automated negotiation among Web services provides an effective way for the services to bargain for their optimal customizations and allows the discovery of overlooked potential solutions. Dynamic and unique Quality of Service (QoS) requirements of diverse service consumers, pose challenges for effective approaches of service compositions with multiple QoS parameters. In this paper, we present a negotiation Web service that would be used by both the consumer and provider Web services for conducting negotiations for dependent QoS parameters. We use a genetic algorithm(GA) based approach for finding multiple Pareto optimal solutions in multi-party and multi-objective negotiation scenarios, that may satisfy user's requirements. Experimental results indicate the applicability of or our approach in facilitating the negotiations involved in a Web service composition process.