The International Code of Nomenclature of Prokaryotes (ICNP) recently underwent some major modifications regarding the higher taxonomic ranks. On the one hand, the phylum category was introduced into the ICNP, which rapidly led to the valid publication of more than forty names of phyla. On the other hand, a decision on the retroactivity of Rule 8 regarding the names of classes was made, which removed most of the nomenclatural uncertainty that had affected those names during the last decade. However, it turned out that a number of names at the ranks of class, order and family are either not validly published or are validly published but illegitimate, although these names occur in the literature and are based on the type genus of a phylum with a validly published name. A closer examination of the literature for these and similar cases indicates that the names are unavailable under the ICNP either because of minor formal errors in the original descriptions, because another name should have been adopted for the taxon when the name was proposed, because of taxonomic uncertainties that were settled in the meantime, or because the names were placed on the list of rejected names. The purpose of this article is to fill the gaps by providing the missing formal descriptions and to ensure that the resulting taxon names are attributed to the original authors who did the taxonomic work.