Service Composition provides a flexible framework for new service construction by integrating atomic services developed independently. Algorithms are needed to select atomic service and service instances with various QoS levels according to some application-dependent performance requirements. Our objective of service selection is to maximize a QoS function under the end-to-end QoS constraints, as well as reducing the complexity and computing cost. In this paper the problem is modeled as a multi-dimension multi-choice 0–1 knapsack problem (MMKP). A novel efficient heuristic algorithm for service selection is presented. This algorithm takes the priority of service components and the priority of QoS attributes. These priorities are useful in promoting the efficiency and reducing the complexity of service selection algorithm. The simulation results show that the improvement on efficiency is obvious and increasing with the number of service components.