Teleost fishes have extra Hox gene clusters owing to shared or lineage-specific genome duplication events in rayfinned fish (actinopterygian) phylogeny. Hence, extrapolating between genome function of teleosts and human or even between different fish species is difficult. We have sequenced and analyzed Hox gene clusters of the Senegal bichir (Polypterus senegalus), an extant representative of the most basal actinopterygian lineage. Bichir possesses four Hox gene clusters (A, B, C, D); phylogenetic analysis supports their orthology to the four Hox gene clusters of the gnathostome ancestor. We have generated a comprehensive database of conserved Hox noncoding sequences that include cartilaginous, lobe-finned, and ray-finned fishes (bichir and teleosts). Our analysis identified putative and known Hox cis-regulatory sequences with differing depths of conservation in Gnathostoma. We found that although bichir possesses four Hox gene clusters, its pattern of conservation of noncoding sequences is mosaic between outgroups, such as human, coelacanth, and shark, with four Hox gene clusters and teleosts, such as zebrafish and pufferfish, with seven or eight Hox gene clusters. Notably, bichir Hox gene clusters have been invaded by DNA transposons and this trend is further exemplified in teleosts, suggesting an as yet unrecognized mechanism of genome evolution that may explain Hox cluster plasticity in actinopterygians. Taken together, our results suggest that actinopterygian Hox gene clusters experienced a reduction in selective constraints that surprisingly predates the teleost-specific genome duplication.