Correlated noise naturally arises in quantum systems due to, e.g., phase and amplitude fluctuations in global control or long-range correlations generated by a many-body sensing target near criticality. In this work, we propose a new form of exponential quantum advantage in the context of sensing correlated noise. Specifically, we focus on the problem of estimating parameters associated with Lindblad dephasing dynamics, and show that entanglement enhancement in the sensitivity (as quantified via quantum Fisher information of the sensor state) arises for estimating the strength of fluctuations in the noise fields’ center-of-mass mode. In the presence of strong background fluctuations, such enhancement grows exponentially with the number of probes in the shot-limited regime, when the measurement and reset operations are slow. This result stands in stark contrast with previously studied scenarios of sensing uncorrelated dephasing noise, where one can prove that entanglement does not lead to an advantage in the signal-to-noise ratio. Our work thus opens a novel pathway towards achieving entanglement-based sensing advantage, which may find applications in characterizing decoherence dynamics of near-term quantum devices. Further, our approach provides a potential quantum-enhanced probe of many-body correlated phases by measuring noise generated by a sensing target. We also discuss realization of our protocol using near-term quantum hardware.