Many-body systems relaxing to equilibrium can exhibit complex dynamics even if their steady state is trivial. In situations where relaxation requires highly constrained local particle rearrangements, such as in glassy systems, this dynamics can be difficult to analyze from first principles. The essential physical ingredients, however, can be captured by idealized lattice models with so-called kinetic constraints. While so far constrained dynamics has been considered mostly as an effective and idealized theoretical description of complex relaxation, here we experimentally realize a many-body system exhibiting manifest kinetic constraints and measure its dynamical properties. In the cold Rydberg gas used in our experiments, the nature of the kinetic constraints can be tailored through the detuning of the excitation lasers from resonance. The system undergoes a dynamics which is characterized by pronounced spatial correlations or anticorrelations, depending on the detuning. Our results confirm recent theoretical predictions, and highlight the analogy between the dynamics of interacting Rydberg gases and that of certain soft-matter systems.