Service selection in service-oriented computing has emerged to be an increasingly important research area. From the client's point of view, in addition to the QoS of a service or a service composition, the trust level becomes an important part. As the complexity of invocation in service composition has been greatly increased, a comprehensive mechanism, which could evaluate both the subjective aspect as trust expression and the objective aspect as QoS, is needed. In this paper, we provide a formal service composition architecture for service selection. In addition, we propose a trust evaluation method for the service composition plan based on the subjective probability theory, based on them, our trust-oriented genetic algorithm (TOGA) is proposed to find a near-optimal service composition plan with QoS constraints. Experimental results have illustrated that our proposed approach can discover the near-optimal solution efficiently. Copyright © 2013 John Wiley & Sons, Ltd.