When moving from monolithic applications towards service-oriented multimedia frameworks, the composition of Web services to form complex multimedia workflows becomes a demanding problem. Especially mobile devices require a flexible composition strategy as they often have to move computationally complex or power-demanding tasks to powerful servers. Such a strategy also has to consider the changing environment due to movements of the device and it has to adapt to device-specific characteristics, e.g., the current battery level. Hence, mobile devices experience problems beyond the mere question of services’ availability or successful execution. We propose the E2Mon algorithm that monitors the execution chain of Web services and gracefully recovers from failures of individual services and network-specific or device-specific alarms. The sophisticated control flow dynamically chooses the quality-optimal and cost-optimal composition of available services handling both successive and parallel service execution.