In today's complex business environment, applications span across loosely coupled systems generating massive amounts of business artifacts at various levels of granularity. Monitoring and analyzing these artifacts enables access to critical process information to improve the effectiveness of business operations. Tracking, capturing, storing and processing such large volumes of data, however, is difficult and resource intensive with current relational database technologies. Hence, designers are forced to make trade-offs in deciding the type and the granularity level of the data to be captured. Nevertheless, the amount of historical data that carries important insight about the business processes that need to be captured is growing. A solution that is capable of handling massive business provenance data is necessary. In this paper, using cloud as opposed to relational databases to manage this massive amount of business provenance data is proposed and a cloud-based business provenance architecture based on HBase/Hadoop technology is introduced. © 2011 IEEE.