We introduce the Space-Time Markov Chain Approximation (STMCA) for a general diffusion process on a finite metric graph $Γ$. The STMCA is a doubly asymmetric (in both time and space) random walk defined on a subdivisions of $Γ$, with transition probabilities and conditional transition times that match, in expectation, those of the target diffusion. We derive bounds on the $p$-Wasserstein distances between the diffusion and its STMCA in terms of a thinness quantifier of the subdivision. This bound shows that convergence occurs at any rate inferior to $\frac{1}{4} \wedge \frac{1}{p} $ in terms of the the maximum cell size of the subdivision, for adapted subdivisions, at any rate inferior to $\frac{1}{2} \wedge \frac{2}{p} $. Additionally, we provide explicit analytical formulas for transition probabilities and times, enabling practical implementation of the STMCA. Numerical experiments illustrate our results.