DNA barcoding using a partial region (648bp) of the cytochrome c oxidase I (COI) gene is a powerful tool for species identification and has revealed many cryptic species in various animal taxa. In birds, cryptic species are likely to occur in insular regions like the Japanese Archipelago due to the prevention of gene flow by sea barriers. Using COI sequences of 234 of the 251 Japanese-breeding bird species, we established a DNA barcoding library for species identification and estimated the number of cryptic species candidates. A total of 226 species (96.6%) had unique COI sequences with large genetic divergence among the closest species based on neighbour-joining clusters, genetic distance criterion and diagnostic substitutions. Eleven cryptic species candidates were detected, with distinct intraspecific deep genetic divergences, nine lineages of which were geographically separated by islands and straits within the Japanese Archipelago. To identify Japan-specific cryptic species from trans-Paleartic birds, we investigated the genetic structure of 142 shared species over an extended region covering Japan and Eurasia; 19 of these species formed two or more clades with high bootstrap values. Excluding six duplicated species from the total of 11 species within the Japanese Archipelago and 19 trans-Paleartic species, we identified 24 species that were cryptic species candidates within and surrounding the Japanese Archipelago. Repeated sea level changes during the glacial and interglacial periods may be responsible for the deep genetic divergences of Japanese birds in this insular region, which has led to inconsistencies in traditional taxonomies based on morphology.