The complexity of interacting quantum many-body systems leads to exceedingly long recurrence times of the initial quantum state for all but the smallest systems. For large systems, one cannot probe the full quantum state in all its details. Thus, experimentally, recurrences can only be determined on the level of the accessible observables. Realizing a commensurate spectrum of collective excitations in one-dimensional superfluids, we demonstrate recurrences of coherence and long-range order in an interacting quantum many-body system containing thousands of particles. Our findings will enable the study of the coherent dynamics of large quantum systems even after they have reached a transient thermal-like state.