The ureilite meteorites are carbonaceous olivine-pyroxene achondrites. They typically contain up to 4 wt.% carbon (carbonaceous matrix) as graphite, diamond, and lonsdaleite. Shock degradation has effectively obliterated primary textures in the carbonaceous matrix of previously described ureilites, a factor that has hampered efforts to explain the origin of this material. In contrast, the Antarctic ureilite ALHA78019 displays perfectly preserved primary textures in the carbonaceous matrix characterized by euhedral graphite blades intergrown with Fe-Ni metal and sulfide (diamonds are absent). This petrographic feature suggests that most graphite in ureilites originated by crystallization from a C-rich metallic phase. Assuming that fO2 is controlled by C--CO--CO2 reactions, the compositions of silicates and metals in ureilites imply a two-stage redox history. The noble gases and rare earths of ureilites are discussed in light of this model.