Two Gram-stain-negative, strictly aerobic, non-motile, rod-shaped bacteria, designated D3-12ᵀ and G2-2ᵀ, were isolated from the phycosphere of marine red algae. Both strains exhibited catalase- and oxidase-positive activities. Strain D3-12ᵀ grew optimally at 30°C, pH 7.0, and 2.0–3.0% (w/v) NaCl, while strain G2-2ᵀ showed optimal growth at 30°C, pH 7.0, and 2.0% NaCl. Ubiquinone-10 was the sole respiratory quinone in both strains. The major fatty acids (> 5%) in strain D3-12ᵀ were feature 8 (C_18:1 ω7c and/or C_18:1 ω6c), 11-methyl-C_18:1 ω7c, and C_16:0, while strain G2-2ᵀ contained summed feature 8 and C_16:0. The predominant polar lipids in strain D3-12ᵀ were phosphatidylcholine, phosphatidylglycerol, and phosphatidylethanolamine, whereas strain G2-2ᵀ contained phosphatidylglycerol and diphosphatidylglycerol. The genomic DNA G + C content was 59.9% for strain D3-12ᵀ and 60.2% for strain G2-2ᵀ. Phylogenetic analyses based on 16S rRNA and whole-genome sequences placed both strains into distinct lineages within the family Roseobacteraceae, separate from previously described genera. Genome-based relatedness metrics, including average nucleotide identity, digital DNA-DNA hybridization, average amino acid identity, and percentage of conserved proteins, further confirmed that these strains represent novel genera. Based on phenotypic, chemotaxonomic, and molecular characteristics, strains D3-12ᵀ and G2-2ᵀ are proposed as novel genera: Phycobium rhodophyticola gen. nov., sp. nov. (D3-12ᵀ = KACC 22712ᵀ = JCM 35528ᵀ) and Aliiphycobium algicola gen. nov., sp. nov. (G2-2ᵀ = KACC 22602ᵀ = JCM 35752ᵀ). Additionally, metabolic features relevant to interactions with marine algae, including genes associated with carbohydrate-active enzymes, vitamin biosynthesis, phenylacetic acid production, and bacterioferritin synthesis, were bioinformatically investigated.