Certain wave functions of non-interacting quantum chaotic systems can exhibit scars in the fabric of their real-space density profile. Quantum scarred wave functions concentrate in the vicinity of unstable periodic classical trajectories. We introduce the notion of many-body quantum scars which reflect the existence of a subset of special many-body eigenstates concentrated in certain parts of the Hilbert space. We demonstrate the existence of scars in the Fibonacci chain -- the one- dimensional model with a constrained local Hilbert space realized in the 51 Rydberg atom quantum simulator [H. Bernien et al., arXiv:1707.04344]. The quantum scarred eigenstates are embedded throughout the thermalizing many-body spectrum, but surprisingly lead to direct experimental signatures such as robust oscillations following a quench from a charge-density wave state found in experiment. We develop a model based on a single particle hopping on the Hilbert space graph, which quantitatively captures the scarred wave functions up to large systems of L = 32 atoms. Our results suggest that scarred many-body bands give rise to a new universality class of quantum dynamics, which opens up opportunities for creating and manipulating novel states with long-lived coherence in systems that are now amenable to experimental study.