This is the final version. Available from American Physical Society via the DOI in this recordThe unknown temperature of a sample can be estimated with minimal disturbance by putting it in thermal contact with an individual quantum probe. If the interaction time is sufficiently long so that the probe thermalizes, the temperature can be read-out directly from its steady state. Here we prove that the optimal quantum probe, acting as a thermometer with maximal thermal sensitivity, is an effective two-level atom with a maximally degenerate excited state. When the total interaction time is insufficient to produce full thermalization, we optimize the estimation protocol by breaking it down into sequential stages of probe preparation, thermal cont...