A novel Gram-negative and rod-shaped bacterium, designated N8T, was isolated from tidal flat sediment. Phylogenetic analysis based on 16S rRNA gene sequences showed that N8T strain is associated with the family Phyllobacteriaceae: two uncultured clones (98.4 and 99.8% 16S rRNA gene sequence similarity) and the genus Mesorhizobium (≤97.0%). The novel strain formed a separate clade with uncultured clones in the phylogenetic tree based on 16S rRNA gene sequences. Cellular fatty acid profiles predominately comprised C18:1 ω7c and C19:0 cyclo ω8c. The major isoprenoid quinone is ubiquinone-10 and genomic DNA G+C content is 53.4 mol%. The polyphasic taxonomic study indicates that the novel strain N8T represents a novel species of the new genus in the family Phyllobacteriaceae, named Aliihoeflea aestuarii. The type strain is N8T (= KCTC 22052T= JCM 15118T= DSM 19536T).