The taxonomic relationships of 10 strains isolated from seaweeds collected from two beaches in Republic of Korea were studied by sequencing and analyses of 16S rRNA genes and whole genomes. For the construction of a more reliable and robust 16S rRNA gene phylogeny, the authentic and nearly complete 16S rRNA gene sequences of all the Microbacterium type strains were selected through pairwise comparison of the sequences contained in several public databases including the List of Prokaryotic names with Standing in Nomenclature (LPSN). The clustering of the ten study strains into five distinct groups was apparent in this single gene-based phylogenetic tree. In addition, the 16S rRNA gene sequences of a few type strains were shown to be incorrectly listed in LPSN. An overall phylogenomic clustering of the genus Microbacterium was performed with a total of 113 genomes by core genome analysis. As a result, nine major (≥ three type strains) and eight minor (two type strains) clusters were defined mostly at gene support index of 92 and mean intra-cluster OrthoANIu of >80.00%. All of the study strains were assigned to a Microbacterium liquefaciens clade and distributed further into four subclusters in the core genome-based phylogenetic tree. In vitro phenotypic assays for physiological, biochemical, and chemotaxonomic characteristics were also carried out with the ten study strains and seven closely related type strains. Comparison of the overall genomic relatedness indices (OGRI) including OrthoANIu and digital DNA–DNA hybridization supported that the study strains constituted four new species of the genus Microbacterium. In addition, some Microbacterium type strains were reclassified as members of preexisting species. Moreover, some of them were embedded in a new genus of the family Microbacteriaceae based on their distinct separation in the core genome-based phylogenetic tree and amino acid identity matrices. Based on the results here, four new species, namely, Microbacterium aurugineum sp. nov., Microbacterium croceum sp. nov., Microbacterium galbinum sp. nov., and Microbacterium sufflavum sp. nov., are described, along with the proposal of Paramicrobacterium gen. nov. containing five reclassified Microbacterium species from the “Microbacterium agarici clade”, with Paramicrobacterium agarici gen. nov., comb. nov. as the type species.