Advancing our understanding of non-equilibrium phenomena in quantum many-body systems remains among the greatest challenges in physics. Here, we report on the experimental observation of a paradigmatic many-body problem, namely the non-equilibrium dynamics of a quantum impurity immersed in a bosonic environment. We use an interferometric technique to prepare coherent superposition states of atoms in a Bose-Einstein condensate with a small impurity-state component, and monitor the evolution of such quantum superpositions into polaronic quasiparticles. These results offer a systematic picture of polaron formation from weak to strong impurity interactions. They reveal three distinct regimes of evolution with dynamical transitions that provide a link between few-body processes and many-body dynamics. Our measurements reveal universal dynamical behavior in interacting many-body systems and demonstrate new pathways to study non-equilibrium quantum phenomena.