Any web service procurement involves complex negotiations on non-functional requirements in order to obtain an integrative solution for both the provider and consumer perspectives. Software that facilitates automated web service procurement negotiations is valuable not only for the consumers and providers to continuously bargain for their customizations and tailor their offerings, but also to discover overlooked alternative solutions and to maintain documented rationales for future references and reuse. To date, software frameworks and mechanisms that provide flexible environments to support automated negotiations in web service procurement are lagging. This paper presents a tradeoff-based automated negotiation approach to support web service procurement. The approach employs an iterative tradeoff mechanism for evaluating opponent's offers and generating counter-offers of mutual gain based on selected quality of service parameters. The paper presents the negotiation approach in details along with an illustrated case study of negotiation in web service procurement for a medical insurance company.