To securely and conveniently enjoy the benefits of cloud storage, it is desirable to design a cloud data storage system which protects data privacy from storage servers through encryption, allows fine-grained access control such that data providers can expressively specify who are eligible to access the encrypted data, enables dynamic user management such that the total number of data users is unbounded and user revocation can be carried out conveniently, supports data provider anonymity and traceability such that a data provider’s identity is not disclosed to data users in normal circumstances but can be traced by a trusted authority if necessary, and equally important, provides secure data provenance by presenting irrefutable evidence on who has created and modified the data in the cloud. However, most of the existing cloud storage systems with secure provenance either lack the expressiveness in access control or incur too much performance overhead or do not support dynamic user management. In this paper, we solve these problems by presenting an attribute-based cloud storage system with secure provenance. We first give a simple construction without achieving user revocation, and then extend it with an efficient revocation mechanism to prevent revoked data users from accessing the newly encrypted data. Thereafter, we implement the algorithms in the proposed two constructions to evaluate their performance. Our experimental results show that the proposed systems are acceptable to be applied in practice.