Geochemical indicators in meteorites imply that most formed under relatively oxidizing conditions. However, some planetary materials, such as the enstatite chondrites, aubrite achondrites, and Mercury, were produced in reduced nebular environments. Because of large-scale radial nebular mixing, comets and other Kuiper Belt objects likely contain some primitive material related to these reduced planetary bodies. Here, we describe an unusual assemblage in a dust particle from comet 81P/Wild 2 captured in silica aerogel by the NASA Stardust spacecraft. The bulk of this ∼20 μm particle is comprised of an aggregate of nanoparticulate Cr-rich magnetite, containing opaque sub-domains composed of poorly graphitized carbon (PGC). The PGC forms conformal shells around tiny 5-15 nm core grains of Fe carbide. The C, N, and O isotopic compositions of these components are identical within errors to terrestrial standards, indicating a formation inside the solar system. Magnetite compositions are consistent with oxidation of reduced metal, similar to that seen in enstatite chondrites. Similarly, the core-shell structure of the carbide + PGC inclusions suggests a formation via FTT reactions on the surface of metal or carbide grains in warm, reduced regions of the solar nebula. Together, the nanoscale assemblage in the cometary particle is most consistent with the alteration of primary solids condensed from a C-rich, reduced nebular gas. The nanoparticulate components in the cometary particle provide the first direct evidence from comets of reduced, carbon-rich regions that were present in the solar nebula.