In an open and dynamic Internet environment, the randomness of Web services with unreliable quality leads to low accuracy of optimization in service composition. Therefore, a global dynamic service composition approach is proposed based on randomness of QoS data and trust evaluation. Firstly, the uncertain outliers which lead to unstable objective QoS are removed, and the true values of objective QoS are estimated. Then, the credibility of the evaluation data from the providers and customers are analyzed to obtain the subjective QoS evaluation of current service. Finally, with the objective and subjective QoS data, the global dynamic service composition model is constructed and the optimal result is calculated. Experiment results with real and simulated data show that the proposed approach significantly improves the stability and accuracy of service composition.