Transition edge sensor microcalorimeters can measure x-ray and gamma-ray energies with very high energy resolution and high photon-collection efficiency. For this technology to reach its full potential in future x-ray observatories, each sensor must be able to measure hundreds or even thousands of photon energies per second. Current "optimal filtering" approaches to achieve the best possible energy resolution work only for photons well isolated in time, a requirement in direct conflict with the need for high-rate measurements. We describe a new analysis procedure to allow fitting for the pulse height of all photons even in the presence of heavy pulse pile-up. In the limit of isolated pulses, the technique reduces to the standard optimal filtering with long records. We employ reasonable approximations to the noise covariance function in order to render multi-pulse fitting computationally viable even for very long data records. The technique is employed to analyze x-ray emission spectra at 600 eV and 6 keV at rates up to 250 counts per second in microcalorimeters having exponential signal decay times of approximately 1.2 ms.