We introduce a framework for describing the real-time dynamics of quantum impurity models out of equilibrium which is based on the influence matrix approach. By replacing the dynamical map of a large fermionic quantum environment with an effective semigroup influence matrix (SGIM) which acts on a reduced auxiliary space, we overcome the limitations of previous proposals, achieving high accuracy at long evolution times. This SGIM corresponds to a uniform matrix-product state representation of the influence matrix and can be obtained by an efficient algorithm presented in this Letter. We benchmark this approach by computing the spectral function of the single impurity Anderson model with high resolution. Further, the spectrum of the effective dynamical map allows us to obtain relaxation rates of the impurity toward equilibrium following a quantum quench. Finally, for a quantum impurity model with on-site two-fermion loss, we compute the spectral function and confirm the emergence of Kondo physics at large loss rates.