Carbon nanostructures formed in the opposed-flow flames of methane- and oxygen-enriched air are studied experimentally using thermophoretic sampling technique and high-resolution transmission electron microscopy (TEM). Reconstructed evolution of soot particles along the burner centerline shows the existence of two characteristic layers. The narrow layer of polydisperse precursor particles is located on the oxidizer side of the stagnation plane. The precursor particles undergo carbonization and agglomeration as they are driven to the stagnation plane forming the layer of mature soot aggregates on the fuel side of the precursor layer. High-resolution TEM imaging performed on precursors and mature soot particles reveals the presence of highly organized carbon nanostructures formed inside the tarlike amorphous condensate by carbonization process. Two characteristic structures are observed. They resemble shapes of carbon onions and carbon nanopolyhedral particles. Multiwalled carbon nanotubes (MWNTs) appeared to be present in the collected samples along with other carbon particulates. TEM imaging reveals incidence of isolated MWNTs, MWNT clusters, and clusters of MWNT with soot and nanopolyhedral particles. The nanotube growth by elongation of partially carbonized nanopolyhedral particles is considered as a possible mechanism of noncatalytic MWNT formation.