A nitrogen-vacancy (NV$^-$) center in a nanodiamond, levitated in high vacuum, has recently been proposed as a probe for demonstrating mesoscopic center-of-mass superpositions cite{Scala2013, Zhang2013} and for testing quantum gravity cite{Albrecht2014}. Here, we study the behavior of optically levitated nanodiamonds containing NV$^-$ centers at sub-atmospheric pressures and show that while they burn in air, this can be prevented by replacing the air with nitrogen. However, in nitrogen the nanodiamonds graphitize below $approx 10$ mB. Exploiting the Brownian motion of a levitated nanodiamond, we extract its internal temperature ($T_i$) and find that it would be detrimental to the NV$^-$ centers spin coherence time cite{Toyli2012}. These values of $T_i$ make it clear that the diamond is not melting, contradicting a recent suggestion cite{Neukirch2015}. Additionally, using the measured damping rate of a levitated nanoparticle at a given pressure, we propose a new way of determining its size.