By using the diffusion Monte Carlo method, we obtained the full phase diagram of $^3$He on top of graphite preplated with a solid layer of $^4$He. All the $^4$He atoms of the substrate were explicitly considered and allowed to move during the simulation. We found that the ground state is a liquid of density 0.007 $pm$ 0.001 AA$^{-2}$, in good agreement with available experimental data. This is significantly different from the case of $^3$He on clean graphite, in which both theory and experiment agree on the existence of a gas-liquid transition at low densities. Upon an increase in $^3$He density, we predict a first-order phase transition between a dense liquid and a registered 7/12 phase, the 4/7 phase being found metastable in our calculations. At larger second-layer densities, a final transition is produced to an incommensurate triangular phase.