As the Web allows information sharing, discovery, aggregation, filtering and flow in an unprecedented manner, it also becomes very difficult to identify, reliably, the original source that produced an information item on the Web. Hence, provenance, i.e., the origin or source of something, is becoming an important concern, since it offers the means to verify data products, to infer their quality, to analyse the processes that led to them, and to decide whether they can be trusted. For instance, provenance enables the reproducibility of scientific results; provenance is necessary to track attribution and credit in curated databases; and, it is essential for reasoners to make trust judgements about the information they use over the Semantic Web. Since the emerging use of provenance in niche applications is undoubtedly demonstrating benefits, this survey contends that provenance can and should reliably be tracked and exploited on the Web.The Foundations for Provenance on the Web is aimed at anyone who discovers or publishes information on the Web, and who cares about its origin and its quality. Based on an analysis of literature, this survey puts forward the Open Provenance Vision, a visionary but pragmatic, integrative conceptual framework allowing the provenance of information to be expressed, tracked, and queried seamlessly, as it crosses information systems across the Web. Some foundational work has already resulted in significant advances in semantics, data models and systems, which can underpin this vision. However, some shortcomings inevitably exist and are discussed. For this vision to succeed, it requires a multi-disciplinary approach, since it requires contributions from many computer science sub-disciplines, but also other non technical fields given the human challenge that is anticipated.