This paper is a position statement of the co-chairs for the First Workshop on Multimedia Service Composition on specific challenges in the area of multimedia service composition. The goal is to present and discuss problems that occur when considering building large scale multimedia systems via service composition. Today the realization of multimedia systems still heavily relies on building monolithic systems. Hence, building complex large scale multimedia systems is always a difficult, costly, time-consuming and challenging problem. Service-based architectures and the possibility to flexibly compose basic services to implement more complex workflows (or rather execution flows), as proposed in the Web and Grid communities, can provide a possible solution to this problem. However, due to the special characteristics of multimedia applications and the rich semantic structure of multimedia data and workflows, Web or Grid-based research results still cannot be readily applied. In this introduction-paper, we summarize challenges that need to be addressed and present a snapshot of the current state of the art towards building large scale multimedia systems.