The process tensor framework to open quantum systems provides the most general description of multi-time correlations in non-Markovian quantum dynamics. A compressed representation of a process tensor in terms of matrix product operators (MPO) can be used for numerically exact calculations of multi-time correlation functions in systems strongly coupled to a non-Markovian reservoir. We show here that the numerical effort for computing multi-dimensional spectra can be significantly improved using a time-translation invariant MPO representation of the process tensor obtained from the uniform time-evolving matrix product operator (uniTEMPO) method. In particular, this approach provides a spectral representation of the non-Markovian dynamics that gives direct access to correlation functions in Fourier-space, avoiding explicit real-time evolution. We calculate linear and 2D electronic spectra for an example system and discuss the performance and numerical scaling of our simulations.