BACKGROUND: Microorganisms able to grow under artificial culture conditions comprise only a small proportion of the biosphere's total microbial community. Until recently, scientists have been unable to perform thorough analyses of difficult-to-culture microorganisms due to limitations in sequencing technology. As modern techniques have dramatically increased sequencing rates and rapidly expanded the number of sequenced genomes, in addition to traditional taxonomic classifications which focus on the evolutionary relationships of organisms, classifications of the genomes based on alternative points of view may help advance our understanding of the delicate relationships of organisms. RESULTS: We have developed a proteome-based method for classifying microbial species. This classification method uses a set of probes comprising short, highly conserved amino acid sequences. For each genome, in silico translation is performed to obtained its proteome, based on which a probe-set frequency pattern is generated. Then, the probe-set frequency patterns are used to cluster the proteomes/genomes. CONCLUSIONS: Features of the proposed method include a high running speed in challenge of a large number of genomes, and high applicability for classifying organisms with incomplete genome sequences. Moreover, the probe-set clustering method is sensitive to the metabolic phenotypic similarities/differences among species and is thus supposed potential for the classification or differentiation of closely-related organisms.