This book constitutes the thoroughly refereed proceedings of the 16th International Workshop on Fast Software Encryption, FSE 2009 held in Leuven, Belgium in February 2009. The 24 revised full papers were carefully reviewed and selected from 76 submissions. The papers are organized in topical sections on stream ciphers, theory of hash functions, block ciphers analysis, block ciphers, theory of symmetric key, and message authentication codes.