The realization of multimedia systems still heavily relies on building monolithic systems that need to be reengineered for every change in the application and little of which can be reused in subsequent developments even for similar applications. Hence, building complex large scale multimedia systems is still a difficult and challenging problem. Service-based architectures, like researched in the Web community, form a possible solution to this problem: The service-based paradigm decomposes complex tasks into smaller independent entities (e.g. Web services), and then supports a flexible service composition in a variety of ways. However, due to the characteristics of multimedia applications and rich semantic structure of multimedia data and workflows, a direct application of Web-based research results is still difficult. The reason is that Web service frameworks cannot yet cope with the complexity of multimedia applications and their metadata. In this paper, we describe a basic taxonomy for the composition of services to support complex multimedia workflows. We will investigate in detail the necessary steps and methodology for multimedia service compositions and apply our taxonomy to different service composition instances. We will illustrate all composition instances within our taxonomy with case studies and point to possible techniques for the composition problem.