In this paper we propose a new mechanism for achieving forward secure encryption in store and for- ward messaging systems such as email and SMS. In a forward secure encryption scheme, a user periodically updates her secret key so that past messages remain confidential in the event that her key is compromised. A primary contribution of our work is to introduce a new form of encryption that we name puncturable encryption. Using a puncturable encryption scheme, recipients may repeatedly update their decryption keys to revoke decryption capability for selected messages, recipients or time periods. Most importantly, this up- date process does not require the recipients to commu- nicate with or distribute new key material to senders. We show how to combine puncturable encryption with the forward-secure public key encryption proposal of Canetti et al. to achieve practical forward-secure messaging with low overhead. We implement our schemes and provide experimental evidence that this new construction is practical.