Precise interferometric measurement is vital to many scientific and technological applications. Using quantum entanglement allows interferometric sensitivity that surpasses the shot-noise limit (SNL). To date, experiments demonstrating entanglement-enhanced sub-SNL interferometry, and most theoretical treatments, have addressed the goal of increasing signal-to-noise ratios. This is suitable for phase-sensing - detecting small variations about an already known phase. However, it is not sufficient for ab initio phase-estimation - making a self-contained determination of a phase that is initially completely unknown within the interval [0, 2π). Both tasks are important, but not equivalent. To move from the sensing regime to the ab initio estimation regime requires a non-trivial phase-estimation algorithm. Here, we implement a 'bottom-up' approach, optimally utilizing the available entangled photon states, obtained by post-selection. This enables us to demonstrate sub-SNL ab initio estimation of an unknown phase by entanglement-enhanced optical interferometry.