Service composition has emerged as a fundamental technique for developing Web applications. Multiple services, often from different organizations or trust domains, may be dynamically composed to satisfy a user's request. Access control in the presence of service compositions is a challenging security problem. In this paper, we present an access control model and techniques for specifying and enforcing access control rules on Web service compositions. A key advantage of our approach is that past histories of service invocations can be used to make access control decisions. Our approach allows role hierarchies and separation of duty constraints. Access controls rules may be parameterized by one or more arguments. We have implemented our access control model via a declarative policy specification language which uses pure-past linear temporal logic (PPLTL).We describe an implementation of our approach using a supply chain management (SCM) application. Our experiments show that our approach can enforce expressive and flexible access control policies while incurring reasonable performance overhead on the application.