The invention discloses a service combination optimization method based on quality of service (QoS) historical records. The method comprises the following steps of: acquiring a data set which consists of the QoS historical records of respective web services; solving previous N optimal combination schemes based on the historical records; calculating a service contribution degree, calculating a contribution degree value of each service by using the previous N optimal combination schemes (generated from the above step) based on the QoS historical records, and selecting the web service which meets the requirement for each task in a service combination; and for the candidate service of each task, selecting the service with the highest contribution degree value to execute the optimal service combination scheme. The method has the advantages that a decision is made by using the QoS historical records of the services, so that the decision is relatively objective and credible; variable parameters of the contribution degrees are supplied; the services which can participate in a final optimal combination scheme can be determined according to the contribution values of the services; and therefore, the credibility of the final combination scheme is relatively high.