Going beyond the linearized study has been a longstanding problem in the theory of Landau damping. In this paper we establish Landau damping for the nonlinear Vlasov equation, for any interaction potential less singular than Coulomb. The damping phenomenon is reinterpreted in terms of transfer of regularity between kinetic and spatial variables, rather than exchanges of energy. 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 nonlinear echoes; sharp scattering estimates; and a Newton approximation scheme. We point out the (a priori unexpected) critical nature of the Coulomb potential and analytic regularity, which can be seen only at the nonlinear level; in this case we derive Landau damping over finite but exponentially long times. Physical implications are discussed.