We have sequenced and analyzed Hox gene clusters from elephant shark, a holocephalian cartilaginous fish. Elephant shark possesses 4 Hox clusters with 45 Hox genes that include orthologs for a higher number of ancient gnathostome Hox genes than the 4 clusters in tetrapods and the supernumerary clusters in teleost fishes. Phylogenetic analysis of elephant shark Hox genes from 7 paralogous groups that contain all of the 4 members indicated an ((AB)(CD)) topology for the order of Hox cluster duplication, providing support for the 2R hypothesis (i.e., 2 rounds of whole-genome duplication during the early evolution of vertebrates). Comparisons of noncoding sequences of the elephant shark and human Hox clusters have identified a large number of conserved noncoding elements (CNEs), which represent putative cis-regulatory elements that may be involved in the regulation of Hox genes. Interestingly, in fugu more than 50% of these ancient CNEs have diverged beyond recognition in the duplicated (HoxA, HoxB, and HoxD) as well as the singleton (HoxC) Hox clusters. Furthermore, the b-paralogs of the duplicated fugu Hox clusters are virtually devoid of unique ancient CNEs. In contrast to fugu Hox clusters, elephant shark and human Hox clusters have lost fewer ancient CNEs. If these ancient CNEs are indeed enhancers directing tissue-specific expression of Hox genes, divergence of their sequences in vertebrate lineages might have led to altered expression patterns and presumably the functions of their associated Hox genes.