With the popularity of mobile services, an effective context-aware mobile service adaptation is becoming more and more important for operators. In this paper, we propose a Co-evolution eXtended Classifier System (CXCS) to perform context-aware mobile service adaptation. Our key idea is to learn user context, match adaptation rule, and provide the best suitable mobile services for users. Different from previous adaptation schemes, our proposed CXCS can produce a new user's initial classifier population to quicken its converging speed. Moreover, it can make the current user to predict which service should be selected, corresponding to an uncovered context. We compare CXCS based on a common mobile service adaptation scenario with other five adaptation schemes. The results show the adaptation accuracy of CXCS is higher than 70% on average, and outperforms other schemes.