Discovery of new phenomena in particle physics would be our best indicator of which beyond the standard model theory is correct. The Tevatron provides the highest energy collisons available and therefore some of our best opportunities to find new physics. I will discuss some of the new search results from D0 including searches for extra dimensions, SUSY and new particles.