Until the LHC gets started, the Tevatron Collider which provides 2 TeV c.m. p-pbar interactions to the CDF and D0 experiments, is the only place to do physics at the high energy frontier. I will review some of the new phenomena searches performed with the D0 detector in order to explore a few directions in possible extensions of the Standard Model of Particle Physics. I will show results obtained in analyses performed with up to 1fb-1 of data of the Run II of the Tevatron.