The morphology of the vertebrate head skeleton is highly plastic, with the number, size, shape, and position of its components varying dramatically between groups. While this evolutionary flexibility has been key to vertebrate success, its developmental and genetic bases are poorly understood. The larval head skeleton of the frog Xenopus laevis possesses a unique combination of ancestral tetrapod features and anuran-specific novelties. We built a detailed gene expression map of the head mesenchyme in X. laevis during early larval development, focusing on transcription factor families with known functions in vertebrate head skeleton development. This map was then compared to homologous gene expression in zebrafish, mouse, and shark embryos to identify conserved and evolutionarily flexible aspects of vertebrate head skeleton development. While we observed broad conservation of gene expression between X. laevis and other gnathostomes, we also identified several divergent features that correlate to lineage-specific novelties. We noted a conspicuous change in dlx1/2 and emx2 expression in the second pharyngeal arch, presaging the differentiation of the reduced dorsal hyoid arch skeletal element typical of modern anamniote tetrapods. In the first pharyngeal arch we observed a shift in the expression of the joint inhibitor barx1, and new expression of the joint marker gdf5, shortly before skeletal differentiation. This suggests that the anuran-specific infrarostral cartilage evolved by partitioning of Meckel's cartilage with a new paired joint. Taken together, these comparisons support a model in which early patterning mechanisms divide the vertebrate head mesenchyme into a highly conserved set of skeletal precursor populations. While subtle changes in this early patterning system can affect skeletal element size, they do not appear to underlie the evolution of new joints or cartilages. In contrast, later expression of the genes that regulate skeletal element differentiation can be clearly linked to the evolution of novel skeletal elements. We posit that changes in the expression of downstream regulators of skeletal differentiation, like barx1 and gdf5, is one mechanism by which head skeletal element number and articulation are altered during evolution.