The great majority of microbial species remains uncultured, severely limiting their taxonomic characterization and thus communication among scientists. Although Candidatus was devised as a provisional category to classify uncultured taxa, it has not been widely accepted owing to technical limitations and lack of priority of Candidatus names in the official nomenclature. High-throughput sequencing provides the potential for data-rich taxonomic descriptions of uncultivated microbes, comparable in quality to those of cultured organisms. In order to fully realize this potential, standards and guidelines on how to perform these descriptions are needed. Here we aimed to outline these standards and draw the roadmap for a new genome-based taxonomy that, at least initially, would be parallel but highly convergent to the one in existence for isolates. In particular, we recommend the use of DNA genome sequences, recovered by population binning or single-cell techniques, as the basis for (i) identification and phylogenetic placement, (ii) bioinformatics-based functional and thus phenotypic predictions, as well as (iii) type material. We also recommend the implementation of an independent nomenclatural system for uncultivated taxa, following the same nomenclature rules as those for cultured Bacteria and Archaea but with its own list of validly published names. If widely adopted, this system will not only facilitate a comprehensive characterization of the 'uncultivated majority', but also provide a unified catalogue of validly published names, thereby avoiding synonyms and confusion. We also suggest that a committee of experts, supported by an international microbiological society, should be formed to govern the new classification system.