We introduce an efficient method to simulate dynamics of an interacting quantum impurity coupled to non-interacting fermionic reservoirs, based on a matrix-product state (MPS) representation of the reservoirs’ Feynman-Vernon influence functionals (IF). The efficiency of such representation rests on the moderate entanglement of the IF viewed as a “temporal state”, dubbed temporal entanglement (TE). By analytically studying TE for a general class of reservoir’s initial states, we establish that for initial states with finite-range correlations TE obeys an area law, whereas Fermi-sea-type initial states yield logarithmic scaling of TE with time, closely related to the scaling of real-space entanglement in (1+1)-dimensional conformal field theory. Hence, we describe an explicit algorithm for converting the IF temporal state to an optimal MPS form, which can be subsequently contracted with arbitrary impurities with modest effort. We apply our method to quantum quenches and transport in a single- and multi-level impurity Anderson model, including highly non-equilibrium setups, and find favorable performance compared to state-of-the-art methods. The polynomial scaling of computational resources required for an accurate computation of dynamics indicates that a broad class of out-of-equilibrium quantum impurity problems are efficiently solvable.