Web service composition (WSC) has emerged as a promising approach to integrating business applications within and across organizational boundaries. One of the major objectives of WSC research is to improve the performance of composite Web services. To this end, alliance information between different services partners has great potential, but has been overlooked by extant approaches to composing Web services. To address the above limitation, we propose an alliance-aware method for WSC in this paper, which incorporates the alliance information in constructing Web services. In addition, we adopt a multi-agent architecture to model and evaluate methods for WSC. Our experiment results reveal a significant impact of alliance information on the performance of WSC. We believe our findings on WSC are important to both WSC researchers and practitioners.