The rapid development of noisy intermediate-scale quantum (NISQ) devices has raised the question of whether or not these devices will find commercial use. Unfortunately, a major shortcoming of many proposed NISQ-amenable algorithms, such as the variational quantum eigensolver (VQE), is coming into view: the algorithms require too many independent quantum measurements to solve practical problems in a reasonable amount of time. This motivates the central question of our work: how might we speed up such algorithms in spite of the impact of error on NISQ computations? We demonstrate on quantum hardware that the estimation of expectation values, a core subroutine of many quantum algorithms including VQE, can be improved in terms of precision and accuracy by using a technique we call Robust Amplitude Estimation. Consequently, this method reduces the runtime to achieve the same mean-squared error compared to the standard prepare-and-measure estimation method. The surprising result is that by using deeper, and therefore more error-prone, quantum circuits, we realize more accurate quantum computations in less time. As the quality of quantum devices improves, this method will provide a proportional reduction in estimation runtime. This technique may be used to speed up quantum computations into the regime of early fault-tolerant quantum computation and aid in the realization of quantum advantage.