The solar system formed from interstellar dust and gas in a molecular cloud. Astronomical observations show that typical interstellar dust consists of amorphous (a-) silicate and organic carbon. Bona fide physical samples for laboratory studies would yield unprecedented insight about solar system formation, but they were largely destroyed. The most likely repositories of surviving presolar dust are the least altered extraterrestrial materials, interplanetary dust particles (IDPs) with probable cometary origins. Cometary IDPs contain abundant submicron a-silicate grains called GEMS (glass with embedded metal and sulfides), believed to be carbon-free. Some have detectable isotopically anomalous a-silicate components from other stars, proving they are preserved dust inherited from the interstellar medium. However, it is debated whether the majority of GEMS predate the solar system or formed in the solar nebula by condensation of high-temperature (>1,300 K) gas. Here, we map IDP compositions with single nanometer-scale resolution and find that GEMS contain organic carbon. Mapping reveals two generations of grain aggregation, the key process in growth from dust grains to planetesimals, mediated by carbon. GEMS grains, some with a-silicate subgrains mantled by organic carbon, comprise the earliest generation of aggregates. These aggregates (and other grains) are encapsulated in lower-density organic carbon matrix, indicating a second generation of aggregation. Since this organic carbon thermally decomposes above ∼450 K, GEMS cannot have accreted in the hot solar nebula, and formed, instead, in the cold presolar molecular cloud and/or outer protoplanetary disk. We suggest that GEMS are consistent with surviving interstellar dust, condensed in situ, and cycled through multiple molecular clouds.