Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010) and motivated by applications in tamper-resilient cryptography, encode messages in a manner so that tampering the codeword causes the decoder to either output the correct message or an uncorrelated message. While this relaxation of error detection is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly non-malleable coding becomes possible against every fixed family of tampering functions that is not too large. We obtain optimal bounds on the capacity of non-malleable codes and present constructions of rate-optimal and efficient non-malleable codes against natural families of adversaries, such as bit-tampering and polynomial-time adversaries.