Magnetic sensors capable of detecting nanoscale volumes of spins allow for non-invasive, element-specific probing(1-3). The error in such measurements is usually reduced by increasing the measurement time, and noise averaging the signal(4,5). However, achieving the best precision requires restricting the maximum possible field strength to much less than the spectral linewidth of the sensor. Quantum entanglement and squeezing can then be used to improve precision (although they are difficult to implement in solid-state environments). When the field strength is comparable to or greater than the spectral linewidth, an undesirable trade-off between field strength and signal precision occurs(1). Here, we implement novel phase estimation algorithms(6-8) on a single electronic spin associated with the nitrogen-vacancy defect centre in diamond to achieve an similar to 8.5-fold improvement in the ratio of the maximum field strength to precision, for field magnitudes that are large (similar to 0.3 mT) compared to the spectral linewidth of the sensor (similar to 4.5 mu T). The field uncertainty in our approach scales as 1/T-0.88, compared to 1/T-0.5 in the standard measurement approach, where T is the measurement time. Quantum phase estimation algorithms have also recently been implemented using a single nuclear spin in a nitrogen-vacancy centre(9). Besides their direct impact on applications in magnetic sensing and imaging at the nanoscale, these results may prove useful in improving a variety of high-precision spectroscopy techniques.