The late 19th century was the beginning of bacterial taxonomy and bacteria were classified on the basis of phenotypic markers. The distinction of prokaryotes and eukaryotes was introduced in the 1960s. Numerical taxonomy improved phenotypic identification but provided little information on the phylogenetic relationships of prokaryotes. Later on, chemotaxonomic and genotypic methods were widely used for a more satisfactory classification. Archaea were first classified as a separate group of prokaryotes in 1977. The current classification of Bacteria and Archaea is based on an operational-based model, the so-called polyphasic approach, comprised of phenotypic, chemotaxonomic and genotypic data, as well as phylogenetic information. The provisional status Candidatus has been established for describing uncultured prokaryotic cells for which their phylogenetic relationship has been determined and their authenticity revealed by in situ probing. The ultimate goal is to achieve a theory-based classification system based on a phylogenetic/evolutionary concept. However, there are currently two contradictory opinions about the future classification of Bacteria and Archaea. A group of mostly molecular biologists posits that the yet-unclear effect of gene flow, in particular lateral gene transfer, makes the line of descent difficult, if not impossible, to describe. However, even in the face of genomic fluidity it seems that the typical geno- and phenotypic characteristics of a taxon are still maintained, and are sufficient for reliable classification and identification of Bacteria and Archaea. There are many well-defined genotypic clusters that are congruent with known species delineated by polyphasic approaches. Comparative sequence analysis of certain core genes, including rRNA genes, may be useful for the characterization of higher taxa, whereas various character genes may be suitable as phylogenetic markers for the delineation of lower taxa. Nevertheless, there may still be a few organisms which escape a reliable classification.