The service-oriented paradigm offers support for engineering service-based systems (SBSs) based on service compositions. The selection of services with the aim to fulfil the quality constraints for SBSs and to achieve the optimisation goals is a critical and challenging issue. In particular, when the quality-of-service (QoS) constraints for a SBS are severe, it is often difficult to find an optimal solution for the SBS. Exploiting the competition among service providers can help SBS developers obtain favourable QoS offers for the component services of SBSs and increase the possibility of finding optimal solutions for the SBSs. In this paper, we present a novel joint optimisation and negotiation approach named Iterative Negotiation for Service Composition (INSC) that supports effective and efficient QoS-aware service selection for SBSs. We evaluate INSC experimentally using example SBSs that are synthetically generated based on a real-world Web service dataset. The experimental results show that INSC can significantly and efficiently increase the possibility of finding optimal solutions in severe service composition scenarios. © 2012 IEEE.