Scientific workflow is an abstraction used to model in silico experiments. Some of these experiments demands high performance computing environments such as clusters and grids. A new computing model called cloud computing is being adopted by the scientific community to execute their scientific experiments. In addition, in order to consider a scientific experiment as scientific, it has to be reproducible, by querying provenance metadata. However, cloud environments are still incipient when we are capturing and storing provenance metadata. This dissertation proposes an approach to support capturing and storing provenance metadata from cloud-based scientific workflows. This approach is coupled to the Matrioshka architecture.