Abstract: As fully fault-tolerant quantum computers capable of solving useful problems remain a future goal, we anticipate an era of ``early fault tolerance'' allowing for limited error correction. We propose a framework for designing early fault-tolerant algorithms by trading between error correction overhead and residual logical noise, and apply it to quantum phase estimation (QPE). We develop a quantum-Fourier-transform (QFT)-based QPE technique that is robust to global depolarising noise and outperforms the previous state of the art at low and moderate noise rates. We further develop a data processing technique, Explicitly Unbiased Maximum Likelihood Estimation (EUMLE), allowing us to mitigate arbitrary error on QFT-based QPE schemes in a consistent, asymptotically normal way. This extends quantum error mitigation techniques beyond expectation value estimation, which was labeled an open problem for the field. Applying this scheme to the ground state problem of the two-dimensional Hubbard model and various molecular Hamiltonians, we find we can roughly halve the number of physical qubits with a ~10x wall-clock time overhead, but further reduction causes a steep runtime increase. This work provides an end-to-end analysis of early fault-tolerance cost reductions and space-time trade-offs, and identifies which areas can be improved in the future.