Typically, the rate at which a heat engine can produce useful work is constrained by the buildup of irreversibility with increasing operating speed. Here, using a recently developed reservoir engineering technique, we designed and quantified the performance of a colloidal Stirling engine operating in a viscoelastic bath. While the bath acts like a viscous fluid in the quasistatic limit, and the engine's performance agrees with equilibrium predictions, on reducing the cycle time to the bath's structural relaxation time, the increasingly elastic response of the bath aids suppress the buildup of irreversibility. We show that the elastic energy stored during the isothermal compression step of the Stirling cycle facilitates quick equilibration in the isothermal expansion step. This results in equilibriumlike efficiencies even for cycle times shorter than the equilibration time of the colloidal particle.