Ever faster changing market conditions require businesses to frequently adapt their business processes and the underlying workflow systems. Serviceoriented architectures are said to deliver this flexibility by loose coupling. In this chapter we provide a survey on realizing flexible workflows on top of service oriented architectures.We show how orchestrations and choreographies may be implemented by state-of-the-art web services technology. The role of agents in realizing workflows among services is discussed. Furthermore, we discuss service provision in dynamic environments, when partners are dynamically bound to the workflow and when changes to the workflow schema happen.