Extra spatial dimensions are proposed by recent theories that postulate the scale of gravity to be of the same order as the electroweak scale. A sizeable interaction between gravitons and Standard Model particles is then predicted. Effects of these new interactions in boson and fermion pair production are searched for in the data sample collected at centre-of-mass energies above the Z pole by the L3 detector at LEP. In addition, the direct production of a graviton associated with a Z boson is investigated. No statistically significant hints for the existence of these effects are found and lower limits in excess of 1 TeV are derived on the scale of this new theory of gravity