For the problem of mobile service selection, this paper gives a context-aware service selection algorithm based on Genetic Algorithm. In this algorithm, a tree encoding method, a fitness function, and a fitness-better strategy were proposed. The tree encoding mode made Genetic Algorithm support selection of various types of service combinations, for example, sequence composition, concurrence composition, probability composition, and loop composition. According to the encoding method, a fitness function was designed specially. The fitness-better strategy gives the direction of population evolution and avoids the degradation of population fitness. Some experiments analyses show that the provided service selection algorithm can get better service composition.