Aerotaxis, the directed migration along oxygen gradients, allows many microorganisms to locate favorable oxygen concentrations. Despite oxygen's fundamental role for life, even key aspects of aerotaxis remain poorly understood. In Bacillus subtilis, for example, there is conflicting evidence of whether migration occurs to the maximal oxygen concentration available or to an optimal intermediate one, and how aerotaxis can be maintained over a broad range of conditions. Using precisely controlled oxygen gradients in a microfluidic device, spanning the full spectrum of conditions from quasi-anoxic to oxic (60 n mol/l-1 m mol/l), we resolved B. subtilis' 'oxygen preference conundrum' by demonstrating consistent migration towards maximum oxygen concentrations ('monotonic aerotaxis'). Surprisingly, the strength of aerotaxis was largely unchanged over three decades in oxygen concentration (131 n mol/l-196 μ mol/l). We discovered that in this range B. subtilis responds to the logarithm of the oxygen concentration gradient, a rescaling strategy called 'log-sensing' that affords organisms high sensitivity over a wide range of conditions. In these experiments, high-throughput single-cell imaging yielded the best signal-to-noise ratio of any microbial taxis study to date, enabling the robust identification of the first mathematical model for aerotaxis among a broad class of alternative models. The model passed the stringent test of predicting the transient aerotactic response despite being developed on steady-state data, and quantitatively captures both monotonic aerotaxis and log-sensing. Taken together, these results shed new light on the oxygen-seeking capabilities of B. subtilis and provide a blueprint for the quantitative investigation of the many other forms of microbial taxis.