The objective of the present study was to provide an updated classification for Burkholderia cepacia complex (Bcc) taxon K isolates. A representative set of 39 taxon K isolates were analyzed through multilocus sequence typing (MLST) and phylogenomic analyses. MLST analysis revealed the presence of at least six clusters of sequence types (STs) within taxon K, two of which contain the type strains of Burkholderia contaminans (ST-102) and Burkholderia lata (ST-101), and four corresponding to the previously defined taxa Other Bcc groups C, G, H and M. This clustering was largely supported by a phylogenomic tree which revealed three main clades. Isolates of B. contaminans and of Other Bcc groups C, G, and H represented a first clade which generally shared average nucleotide identity (ANI) and average digital DNA-DNA hybridization (dDDH) values at or above the 95-96% ANI and 70% dDDH thresholds for species delineation. A second clade consisted of Other Bcc group M bacteria and of four B. lata isolates and was supported by average ANI and dDDH values of 97.2 and 76.1% within this clade and average ANI and dDDH values of 94.5 and 57.2% toward the remaining B. lata isolates (including the type strain), which represented a third clade. We therefore concluded that isolates known as Other Bcc groups C, G, and H should be classified as B. contaminans, and propose a novel species, Burkholderia aenigmatica sp. nov., to accommodate Other Bcc M and B. lata ST-98, ST-103, and ST-119 isolates. Optimized MALDI-TOF MS databases for the identification of clinical Burkholderia isolates may provide correct species-level identification for some of these bacteria but would identify most of them as B. cepacia complex. MLST facilitates species-level identification of many taxon K strains but some may require comparative genomics for accurate species-level assignment. Finally, the inclusion of Other Bcc groups C, G, and H into B. contaminans affects the phenotype of this species minimally and the proposal to classify Other Bcc group M and B. lata ST-98, ST-103, and ST-119 strains as a novel Burkholderia species is supported by a distinctive phenotype, i.e., growth at 42°C and lysine decarboxylase activity.