Going beyond the linearized study has been a longstanding problem in the theory of Landau damping. In this paper we establish exponential Landau damping in analytic regularity. The damping phenomenon is reinterpreted in terms of transfer of regularity between kinetic and spatial variables, rather than exchanges of energy; phase mixing is the driving mechanism. The analysis involves new families of analytic norms, measuring regularity by comparison with solutions of the free transport equation; new functional inequalities; a control of non-linear echoes; sharp "deflection" estimates; and a Newton approximation scheme. Our results hold for any potential no more singular than Coulomb or Newton interaction; the limit cases are included with specific technical effort. As a side result, the stability of homogeneous equilibria of the non-linear Vlasov equation is established under sharp assumptions. We point out the strong analogy with the KAM theory, and discuss physical implications. Finally, we extend these results to some Gevrey (non-analytic) distribution functions. © 2011 Institut Mittag-Leffler.