Multimedia applications are becoming more and more popular on today’s Internet. Given the enormous development costs and less flexibility, traditional monolithic based approaches are not suitable for building large-scale multimedia systems. By composing of distributed, autonomous services dynamically to provide more complex tasks, service composition provides an attractive way for building large-scale Internet applications. So, multimedia service composition provides a viable solution to large-scale complex multimedia systems. One of the challenging issues of multimedia service composition is how to find service paths to route the data flows through while meeting the applications’ resource requirements and specific QoS constraints. However, QoS-aware service routing problem is typically NP-hard. In this paper, we propose a heuristic algorithm named Greedy-EF to solve this problem more effectively. More specially, Greedy-EF uses an aggregate function to evaluate the QoS conditions for each service instance, and a hop-by-hop service selection approach to explore the proper service path. Simulations show that Greedy-EF algorithm can achieve desired QoS assurances as well as load balancing in multimedia service overlay networks.