Phase estimation algorithms are key protocols in quantum information processing. Besides applications in quantum computing, they can also be employed in metrology as they allow for fast extraction of information stored in the quantum state of a system. Here, we implement two suitably modified phase estimation procedures, the Kitaev and the semiclassical Fourier-transform algorithms, using an artificial atom realized with a superconducting transmon circuit. We demonstrate that both algorithms yield a flux sensitivity exceeding the classical shot-noise limit of the device, allowing one to approach the Heisenberg limit. Our experiment paves the way for the use of superconducting qubits as metrological devices which are potentially able to outperform the best existing flux sensors with a sensitivity enhanced by few orders of magnitude.