We establish asymptotic upper and lower bounds for the Wasserstein distance of any order $p\ge 1$ between the empirical measure of a fractional Brownian motion on a flat torus and the uniform Lebesgue measure. Our inequalities reveal an interesting interaction between the Hurst index $H$ and the dimension $d$ of the state space, with a "phase-transition" in the rates when $d=2+1/H$, akin to the Ajtai-Komlós-Tusnády theorem for the optimal matching of i.i.d. points in two-dimensions. Our proof couples PDE's and probabilistic techniques, and also yields a similar result for discrete-time approximations of the process, as well as a lower bound for the same problem on $\mathbb{R}^d$.