Quantum-mechanical wave-particle duality implies that probability distributions for granular detection events exhibit wave-like interference. On the single-particle level, this leads to self-interference--e.g., on transit across a double slit--for photons as well as for large, massive particles, provided that no which-way information is available to any observer, even in principle. When more than one particle enters the game, their specific many-particle quantum features are manifested in correlation functions, provided the particles cannot be distinguished. We are used to believe that interference fades away monotonically with increasing distinguishability--in accord with available experimental evidence on the single- and on the many-particle level. Here, we demonstrate experimentally and theoretically that such monotonicity of the quantum-to-classical transition is the exception rather than the rule whenever more than two particles interfere. As the distinguishability of the particles is continuously increased, different numbers of particles effectively interfere, which leads to interference signals that are, in general, nonmonotonic functions of the distinguishability of the particles. This observation opens perspectives for the experimental characterization of many-particle coherence and sheds light on decoherence processes in many-particle systems.