Pharyngeal arches are a key innovation that likely contributed to the evolution of the jaws and braincase of vertebrates. It has long been hypothesized that the pharyngeal (branchial) arch evolved from an unjointed cartilaginous rod in vertebrate ancestors such as that in the nonvertebrate chordate amphioxus, but whether such ancestral anatomy existed remains unknown. The pharyngeal skeleton of controversial Cambrian animals called yunnanozoans may contain the oldest fossil evidence constraining the early evolution of the arches, yet its correlation with that of vertebrates is still disputed. By examining additional specimens in previously unexplored techniques (for example, x-ray microtomography, scanning and transmission electron microscopy, and energy dispersive spectrometry element mapping), we found evidence that yunnanozoan branchial arches consist of cellular cartilage with an extracellular matrix dominated by microfibrils, a feature hitherto considered specific to vertebrates. Our phylogenetic analysis provides further support that yunnanozoans are stem vertebrates.