The origin of vertebrate paired appendages is one of the most investigated and debated examples of evolutionary novelty. Paired appendages are widely considered key innovations that allowed new opportunities for controlled swimming and gill ventilation and were prerequisites for the eventual transition from water to land. The last 150 years of debate has been shaped by two contentious theories: the ventrolateral fin-fold hypothesis and the archipterygium hypothesis. The latter proposes that fins and girdles evolved from an ancestral gill arch. Although tantalizing developmental evidence has revived interest in this idea, it is apparently unsupported by fossil evidence. Here we present fossil evidence of a pharyngeal basis for the vertebrate shoulder girdle. We use CT scanning to reveal details of the braincase of Kolymaspis sibirica, a placoderm fish from the Early Devonian of Siberia that suggests a pharyngeal component of the shoulder. We combine these findings with refreshed comparative anatomy of placoderms and jawless outgroups to place the origin of the shoulder girdle on the sixth branchial arch. These findings provide a novel framework for understanding the origin of the pectoral girdle. Our new evidence clarifies the location of the presumptive head-trunk interface in jawless fishes and explains the constraint on branchial arch number in gnathostomes. The results revive a key aspect of the archipterygium hypothesis, but also reconciles it with the ventrolateral fin fold model.