We show that for every ε > 0 there exists a sufficiently large d₀ ∈ ℕ such that for every d ≥ d₀, whp the random d-regular graph G(n,d) contains a T-factor for every tree T on at most (1-ε)d/log d vertices. This is best possible since, for large enough integer d, whp G(n,d) does not contain a ((1+ε)d)/(log d)-star-factor. Our method gives a randomised algorithm which whp finds said T-factor and whose expected running time is O(n^{1+o(1)}), as well as an efficient deterministic counterpart.