The service-oriented paradigm offers support for engineering service-based systems (SBSs) based on service composition where existing services are composed to create new services. The selection of services with the aim to fulfil the quality constraints becomes critical and challenging to the success of SBSs, especially when the quality constraints are stringent. However, none of the existing approaches for quality-aware service composition has sufficiently considered the following two critical issues to increase the success rate of finding a solution: 1) the complementarities between services; and 2) the competition among service providers. This paper proposes a novel approach called combinatorial auction for service selection (CASS) to support effective and efficient service selection for SBSs based on combinatorial auction. In CASS, service providers can bid for combinations of services and apply discounts or premiums to their offers for the multi-dimensional quality of the services. Based on received bids, CASS attempts to find a solution that achieves the SBS owner's optimisation goal while fulfilling all quality constraints for the SBS. When a solution cannot be found based on current bids, the auction iterates so that service providers can improve their bids to increase their chances of winning. This paper systematically describes the auction process and the supporting mechanisms. Experimental results show that by exploiting the complementarities between services and the competition among service providers, CASS significantly outperforms existing quality-aware service selection approaches in finding optimal solutions and guaranteeing system optimality. Meanwhile, the duration and coordination overhead of CASS are kept at satisfactory levels in scenarios on different scales. © 2014 IEEE.