© 2015 American Physical Society. ©2015 American Physical Society.We address the use of entangled qubits as quantum probes to characterize the noise induced by complex environments. In particular, we show that a joint measurement on entangled probes can improve estimation of the correlation time for a broad class of environmental noises compared to sequential strategies involving single-qubit preparation. The enhancement appears when the noise is faster than a threshold value, a regime which may always be achieved by tuning the coupling between the quantum probe and the environment inducing the noise. Our scheme exploits time-dependent sensitivity of quantum systems to decoherence and does not require dynamical control on the probes. We derive the optimal interaction time and the optimal probe preparation, showing that it corresponds to multiqubit Greenberger-Horne-Zeilinger states when entanglement is useful. We also show the robustness of the scheme against depolarization or dephasing of the probe, and discuss simple measurements approaching optimal precision.