Six Gram-negative, rod-shaped, non-spore-forming bacterial strains were isolated from small holes on plaster walls of the stone chamber interior of the Kitora Tumulus in Asuka village, Nara Prefecture, Japan. These were investigated by means of a polyphasic approach. All the isolates were strictly aerobic and motile by peritrichous flagella. Phylogenetic trees generated based on 16S rRNA gene sequences identified two novel lineages (comprising five isolates and one isolate, respectively) within the genus Gluconacetobacter. The isolates were characterized by having Q-10 as the major ubiquinone system and C(18:1)ω7c (58.7-63.1% of the total) as the predominant fatty acid. DNA-DNA hybridization experiments endorsed the species rank for the two lineages, for which the names Gluconacetobacter tumulicola sp. nov. (type strain K5929-2-1b(T) = JCM 17774(T) = NCIMB 14760(T)) and Gluconacetobacter asukensis sp. nov. (type strain K8617-1-1b(T) = JCM 17772(T) = NCIMB 14759(T)) are proposed.