The curvature perturbations produced during an early era of inflation are known to have quasi-Gaussian distribution functions close to their maximum, where they are well constrained by measurements of the cosmic microwave background anisotropies and of the large-scale structures. In contrast, the tails of these distributions are poorly known, although this part is the relevant one for rare, extreme objects such as primordial black holes. We show that these tails are highly non-Gaussian, and cannot be described with standard non-Gaussian expansions, that are designed to approximate the distributions close to their maximum only. Using the stochastic-$\delta N$ formalism, we develop a generic framework to compute the tails, which are found to have an exponential, rather than Gaussian, decay. These exponential tails are inevitable, and do not require any non-minimal feature as they simply result from the quantum diffusion of the inflaton field along its potential. We apply our formalism to a few relevant single-field, slow-roll inflationary potentials, where our analytical treatment is confirmed by comparison with numerical results. We discuss the implications for the expected abundance of primordial black holes in these models, and highlight that it can differ from standard results by several orders of magnitude. In particular, we find that potentials with an inflection point overproduce primordial black holes, unless slow roll is violated.