Service Level Agreement (SLA) negotiations are capable of helping define the quality of service in order to meet the customer’s service requirements. To date, a large number of negotiation protocols are proposed to handle single SLA negotiations, but little work can be found in handling multiple interdependent SLA negotiations in dynamic negotiation environments. This paper proposes an adaptive protocol for concurrently handling multiple interdependent SLA negotiations in dynamic environments. First, interdependencies between SLA negotiations are represented by a graph-based model. Then, an updating mechanism is proposed to handle the dynamism of multiple SLA negotiations. By applying the proposed updating mechanism, a protocol for concurrently processing SLA negotiations in dynamic environments with unexpected changes of service requests is presented. Experimental results show that the proposed approach can effectively handle unexpected changes of service requests from customers in dynamic environments, and successfully lead multiple SLA negotiations to agreements aligning with customers.