The gut microbiota is considered to play a key role in human health. As a consequence, deciphering its microbial diversity is mandatory. A polyphasic taxonogenomic strategy based on the combination of phenotypic and genomic analyses was used to characterize a new bacterium, strain Marseille-P2911. This strain was isolated from a left colon sample of a 60-year old man who underwent a colonoscopy for an etiological investigation of iron-deficiency anemia in Marseille, France. On the basis of 16S rRNA sequence comparison, the closest phylogenetic neighbor was Anaeroglobus geminatus (94.59% 16S rRNA gene sequence similarity) within the family Veillonellaceae. Cells were anaerobic, Gram-stain-positive, non-spore-forming, catalase/oxidase negative cocci grouped in pairs. The bacterium was able to grow at 37 °C after 2 days of incubation. Strain Marseille-P2911 exhibited a genome size of 1,715,864-bp with a 50.2% G + C content, and digital DNA-DNA hybridization (dDDH) and OrthoANI values with A. geminatus of only 19.1 ± 4.5% and 74.42%, respectively. The latter value being lower than the threshold for genus delineation (80.5%), we propose the creation of the new genus Colibacter gen. nov., with strain Marseille-P2911^T (=DSM 103304 = CSUR P2911) being the type strain of the new species Colibacter massiliensis gen. nov., sp. nov.