Today, it is safe to assume that any program or data can be compromised, if they are not protected by hardware within a secure area. Systems based on crypto-processors (e.g., a trusted platform module, a smart card or a hardware security module) rely on the properties of tamper resistant hardware to establish a tight security parameter around a reduced set of predefined functionalities. Such systems are very secure, but they impose strong constraints on the functionalities, the connectivity or the resources available within the secure area. They have not proven versatile enough to provide mainstream trusted storage for personal data. We believe that this role can be taken over by systems equipped with Trusted Execution Environments (TEE), such as ARM’s TrustZone. Indeed, even if TEEs provide weaker security guarantees than crypto-processors, they already provide a secure area on many personal devices. With the advent of programming frameworks for TEEs, interesting services can now be provided on top of a basic encryption/decryption service. In this paper, we describe our implementation of a trusted storage service within a TEE, we analyze its security and show that it can scale. We derive our design from a set of general principles for TEE-Based trusted storage, which we believe constitutes a promising avenue for future research.