Service-oriented architecture is becoming a major software framework for complex application and it can be dynamically and flexibly composed by integrating existing component web services provided by different providers with standard protocols. The rapid introduction of new web services into a dynamic business environment can adversely affect the service quality and user satisfaction. Therefore, how to leverage, aggregate and make use of individual component’s quality of service (QoS) information to derive the optimal QoS of the composite service which meets the needs of users is still an ongoing hot research problem. This study aims at reviewing the advance of the current state-of-the-art in technologies and inspiring the possible new ideas for web service selection and composition, especially with nature-inspired computing approaches. Firstly, the background knowledge of web services is presented. Secondly, various nature-inspired web selection and composition approaches are systematically reviewed and analysed for QoS-aware web services. Finally, challenges, remarks and discussions about QoS-aware web service composition are presented.