In the Virtual Observatory era, where we intend to expose scientists (or software agents on their behalf) to a stream of observations from all existing facilities, the ability to access and to further interpret the origin, relationships, and processing steps on archived astronomical assets (their Provenance) is a requirement for proper observation selection, and quality assessment. In this article we present the different use cases Data Provenance is needed for, the challenges inherent to building such a system for the ESO archive, and their link with ongoing work in the International Virtual Observatory Alliance (IVOA).