In advanced service oriented systems, service provider usually provides value-added composite service to its consumer through compositing some other component service. Because composite service and component services are owned by different organizations and have their own objectives, Service Level Agreements (SLAs) between them should be negotiated to discipline the ways in which services are provided by component services and, in turn, the obligation to be fulfilled by composite services. However, current negotiation approaches for composite service can’t efficiently optimize the preference of composite service and the profits of component services as far as possible. In this paper, we model the negotiation problem for composite service as an optimization problem, and a history heuristic algorithm is proposed to search a (sub-) optimal solution. The SLAs created through this approach optimize the preference and the profits because the negotiation model regards the value of preference and the profits as the objective of optimization. And this approach is efficient for the reason that the times of negotiation are reduced greatly through utilizing the heuristic historical negotiation data. Empirical study shows that, SLAs with (sub-) optimal preference and profits can be found through this approach, and experimental results indicate that the history heuristic based negotiation algorithm proposed in this paper is efficient comparing with the Simulated Annealing based negotiation algorithm.