Web services are a popular choice for component oriented systems that support dynamic compositions. 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. Unique and dynamic Quality of Service (QoS) requirements of 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 acceptable solutions in multi-party and multi-objective scenarios. Experimental results indicate the applicability and improved performance or our approach in facilitating the negotiations involved in a Web service composition process.