<p>Quantum sensors based on critical many-body systems are known to exhibit enhanced sensing capability. Such enhancements typically scale algebraically with the probe size. Going beyond algebraic advantage and reaching exponential scaling has remained elusive when all the resources, such as the preparation time, are taken into account. In this work, we show that many-body systems featuring first order quantum phase transitions can indeed achieve exponential scaling of sensitivity, thanks to their exponential energy gap closing. Remarkably, even after considering the preparation time using local adiabatic driving, the exponential scaling is sustained. Our results are demonstrated through comprehensive analysis of three paradigmatic models exhibiting first order phase transitions, namely Grover, <i>p</i>-spin, and biclique models. We show that this scaling survives moderate decoherence during state preparation and also can be optimally measured in experimentally available basis. Our findings comply with the fundamental bounds and we show that one can harness the exponential advantage through an adaptive strategy even away from the phase transition point.</p>