Vertebrate genomes contain thousands of conserved noncoding elements (CNEs) that often function as tissue-specific enhancers. In this study, we have identified CNEs in human, dog, chicken, Xenopus, and four teleost fishes (zebrafish, stickleback, medaka, and fugu) using elephant shark, a cartilaginous vertebrate, as the base genome and investigated the evolution of these ancient vertebrate CNEs (aCNEs) in bony vertebrate lineages. Our analysis shows that aCNEs have been evolving at different rates in different bony vertebrate lineages. Although 78-83% of CNEs have diverged beyond recognition ("lost") in different teleost fishes, only 24% and 40% have been lost in the chicken and mammalian lineages, respectively. Relative rate tests of substitution rates in CNEs revealed that the teleost fish CNEs have been evolving at a significantly higher rate than those in other bony vertebrates. In the ray-finned fish lineage, 68% of aCNEs were lost before the divergence of the four teleosts. This implicates the "fish-specific" whole-genome duplication in the accelerated evolution and the loss of a large number of both copies of duplicated CNEs in teleost fishes. The aCNEs are rich in tissue-specific enhancers and thus many of them are likely to be evolutionarily constrained cis-regulatory elements. The rapid evolution of aCNEs might have affected the expression patterns driven by them. Transgenic zebrafish assay of some human CNE enhancers that have been lost in teleosts has indicated instances of conservation or changes in trans-acting factors between mammals and fishes.