In today's world, information is increasingly created, processed, transmitted, and stored digitally. While the digital nature of information has brought enormous benefits, it has also created new vulnerabilities and attacks against data. Unlike physical documents, digitally stored information can be rapidly copied, erased, or modified. The distributed nature of today's computing systems also implies that digital data may be stored in or transmitted via untrusted systems. In many cases, even insiders can have financial or strategic motives to tamper with data. Thus, throughout its lifecycle, data may be exposed to many modifications, and be processed by many principals, some of whom may not be trustworthy. In order to trust data, it is therefore useful to know its history, and to protect data history from illicit modifications. Widespread use of electronic records in high-stakes applications such as business and health-care means that the need to ensure trustworthiness of data retention is crucial. Society as a whole will benefit significantly from the development and adoption of techniques for ensuring the integrity of data history, as such assurances will increase public trust in electronic records. In this dissertation, we explore techniques for providing integrity assurances for the history of data in an untrusted environment. We show that it is possible to provide strong integrity assurances for data history, without incurring high performance overheads, or using costly trusted hardware. We first focus on file systems and data provenance, and develop provably-secure schemes for securing file provenance information. With empirical evaluation using realistic file system workloads, we show that our scheme has low overhead, and can be deployed with minimal changes to existing applications. Next, we investigate history integrity in database systems. We develop an efficient, low-overhead architecture for making databases tamper-evident, and provide audit optimizations that make audits very fast. Finally, we examine legal requirements for database integrity, develop a trustworthy and verifiable vacuuming scheme for databases, and show how to define and implement enforcement of subpoenas on database content that is relevant to litigation. [The dissertation citations contained here are published with the permission of ProQuest LLC. Further reproduction is prohibited without permission. Copies of dissertations may be obtained by Telephone (800) 1-800-521-0600. Web page: http://www.proquest.com.bibliotheek.ehb.be/en-US/products/dissertations/individuals.shtml.]