Despite a surface dominated by carbon-based life, the bulk composition of the Earth is dramatically carbon poor when compared to the material available at formation. Bulk carbon deficiency extends into the asteroid belt representing a fossil record of the conditions under which planets are born. The initial steps of planet formation involve the growth of primitive sub-micron silicate and carbon grains in the Solar Nebula. We present a solution wherein primordial carbon grains are preferentially destroyed by oxygen atoms ignited by heating due to stellar accretion at radii < 5 AU. This solution can account for the bulk carbon deficiency in the Earth and meteorites, the compositional gradient within the asteroid belt, and for growing evidence for similar carbon deficiency in rocks surrounding other stars.