Dynamic service-oriented environments (SOEs) are characterised by a large number of heterogeneous service components that are expected to support the business as a whole. The present work provides a negotiation-based approach to facilitate automated and multi-level service-level management in an SOE, where each component autonomously arranges its contribution to the whole operational goals. Evaluation experiments have shown an increased responsiveness and stability of an SOE in case of changes.