© 2019 authors. Published by the American Physical Society. We present a contact-based model to study the spreading of epidemics by means of extending the dynamic message-passing approach to temporal networks. The shift in perspective from node-to edge-centric quantities enables accurate modeling of Markovian susceptible-infected-recovered outbreaks on time-varying trees, i.e., temporal networks with a loop-free underlying topology. On arbitrary graphs, the proposed contact-based model incorporates potential structural and temporal heterogeneities of the contact network and improves analytic estimations with respect to the individual-based (node-centric) approach at a low computational and conceptual cost. Within this new framework, we derive an analytical expression for the epidemic threshold on temporal networks and demonstrate the feasibility of this method on empirical data.