Services in commercial or scientific environments often need to be delivered at a guaranteed service level. This becomes even more important, if composition of services is required, as results will become available for the requester within a predictable timeframe only if the orchestration process may create Service Level Agreements (SLAs) for the individual services. WS-Agreement is a proposed recommendation of the Open Grid Forum (OGF) defining a language and a protocol to create SLAs. As the current version of the specification of WS-Agreement provides only a simple, one-step approach for the creation of SLAs the GRAAP working group of the OGF started working on a more sophisticated protocol allowing multi-step negotiations to create agreements. In this paper we present the approach for negotiations of SLAs using WS-Agreement under specification at the OGF. We describe the state of the work and give an outlook of the next steps until the specification will become a proposed recommendation.