The exponential fitting problem appears in diverse applications such as magnetic resonance spectroscopy, mechanical resonance, chemical reactions, system identification, and radioactive decay. In each application, the exponential fitting problem decomposes measurements into a sum of exponentials with complex coefficients plus noise. Although exponential fitting algorithms have existed since the invention of Prony's Method in 1795, the modern challenge is to build algorithms that stably recover statistically optimal estimates of these complex coefficients while using millions of measurements in the presence of noise. Existing variants of Prony's Method prove either too expensive, most scaling cubically in the number of measurements, or too unstable. Nonlinear least squares methods scale linearly in the number of measurements, but require well-chosen initial estimates lest these methods converge slowly or find a spurious local minimum. We provide an analysis connecting the many variants of Prony's Method that have been developed in different fields over the past 200 years. This provides a unified framework that extends our understanding of the numerical and statistical properties of these algorithms. We also provide two new algorithms for exponential fitting that overcome several practical obstacles. The first algorithm is a modification of Prony's Method that can recover a few exponential coefficients from measurements containing thousands of exponentials, scaling linearly in the number of measurements. The second algorithm compresses measurements onto a subspace that minimizes the covariance of the resulting estimates and then recovers the exponential coefficients using an existing nonlinear least squares algorithm restricted to this subspace. Numerical experiments suggest that small compression spaces can be effective; typically we need fewer than 20 compressed measurements per exponential to recover the parameters with 90% efficiency. We demonstrate the efficacy of this approach by applying these algorithms to examples from magnetic resonance spectroscopy and mechanical vibration. Finally, we use these new algorithms to help answer outstanding questions about damping in mechanical systems. We place a steel string inside vacuum chamber and record the free response at multiple pressures. Analyzing these measurements with our new algorithms, we recover eigenvalue estimates as a function of pressure that illuminate the mechanism behind damping.