High-frequency hearing is required for echolocating bats to locate, range and identify objects, yet little is known about its molecular basis. The discovery of a high-frequency hearing-related gene, KCNQ4, provides an opportunity to address this question. Here, we obtain the coding regions of KCNQ4 from 15 species of bats, including echolocating bats that have higher frequency hearing and non-echolocating bats that have the same ability as most other species of mammals. The strongly supported protein-tree resolves a monophyletic group containing all bats with higher frequency hearing and this arrangement conflicts with the phylogeny of bats in which these species are paraphyletic. We identify five parallel evolved sites in echolocating bats belonging to both suborders. The evolutionary trajectories of the parallel sites suggest the independent gain of higher frequency hearing ability in echolocating bats. This study highlights the usefulness of convergent or parallel evolutionary studies for finding phenotype-related genes and contributing to the resolution of evolutionary problems.