The high-precision interferometric measurement of an unknown phase is the basis for metrology in many areas of science and technology. Quantum entanglement provides an increase in sensitivity, but present techniques have only surpassed the limits of classical interferometry for the measurement of small variations about a known phase. Here we introduce a technique that combines entangled states with an adaptive algorithm to precisely estimate a completely unspecified phase, obtaining more information per photon that is possible classically. We use the technique to make the first ab initio entanglement-enhanced optical phase measurement. This approach will enable rapid, precise determination of unknown phase shifts using interferometry.