The use of quantum resources can provide measurement precision beyond the shot-noise limit (SNL). The task of ab initio optical phase measurement-the estimation of a completely unknown phase-has been experimentally demonstrated with precision beyond the SNL, and even scaling like the ultimate bound, the Heisenberg limit (HL), but with an overhead factor. However, existing approaches have not been able-even in principle-to achieve the best possible precision, saturating the HL exactly. Here we demonstrate a scheme to achieve true HL phase measurement, using a combination of three techniques: entanglement, multiple samplings of the phase shift, and adaptive measurement. Our experimental demonstration of the scheme uses two photonic qubits, one double passed, so that, for a successful coincidence detection, the number of photon-passes is N = 3. We achieve a precision that is within 4% of the HL. This scheme can be extended to higher N and other physical systems.