Whereas the gill chambers of extant jawless vertebrates (lampreys and hagfish) open directly into the environment, jawed vertebrates evolved skeletal appendages that promote the unidirectional flow of oxygenated water over the gills. A major anatomical difference between the two jawed vertebrate lineages is the presence of a single large gill cover in bony fishes versus separate covers for each gill chamber in cartilaginous fishes. Here we find that these divergent gill cover patterns correlate with the pharyngeal arch expression of Pou3f3 orthologs. We identify a Pou3f3 arch enhancer that is deeply conserved from cartilaginous fish through humans but undetectable in lampreys, with minor sequence differences in the bony versus cartilaginous fish enhancers driving the corresponding single versus multiple gill arch expression patterns. In zebrafish, loss of Pou3f3 gene function disrupts gill cover formation, and forced expression of Pou3f3b in the gill arches generates ectopic skeletal elements resembling the multiple gill cover pattern of cartilaginous fishes. Emergence of this Pou3f3 enhancer >430 mya and subsequent modifications may thus have contributed to the acquisition and diversification of gill covers and respiratory strategies during gnathostome evolution.