The utility of near-term quantum computers and simulators is likely to rely upon software-hardware co-design, with error-aware algorithms and protocols optimized for the platforms they are run on. Here, we report on a dominant source of decoherence in trapped ion systems and its implications for quantum simulation. We find that Markovian heating of the ions’ collective motion due to electric field fluctuations causes non-Markovian noise in computations based on internal ion states. Importantly, the temporal correlations of the noise limit the fidelity of Hamiltonian simulation algorithms and induce an optimal gate count, which we demonstrate in the context of a spectrum inference algorithm. We show how an understanding of the noise model can be used to improve the accuracy of Hamiltonian simulation via a tailored feed-forward correction.