  We analyze the potentiality of the new generation of $e^+e^-$ linear
colliders to search for large extra dimensions via the production of fermion
pairs in association with Kaluza-Klein gravitons (G), i.e. $e^+e^- \leftarrow
f\bar{f}G$. This process leads to a final state exhibiting a significant amount
of missing energy in addition to acoplanar lepton or jet pairs. We study in
detail this reaction using full tree level contibutions due to the graviton
emission and the standard model backgrounds. After choosing the cuts to enhance
the signal, we show that a linear collider with a center-of-mass energy of 500
GeV will be able to probe quantum gravity scales from 0.96(0.86) up to 4.1(3.3)
TeV at 2(5)$\sigma$ level, depending on the number of extra dimensions.
