Rhizobiales and related orders of Alphaproteobacteria comprise several genera of nodule-inducing symbiotic bacteria associated with plant roots. Here we describe the genome and the metabolic network of "Candidatus Phaeomarinobacter ectocarpi" Ec32, a member of a new candidate genus closely related to Rhizobiales and found in association with cultures of the filamentous brown algal model Ectocarpus. The "Ca. P. ectocarpi" genome encodes numerous metabolic pathways that may be relevant for this bacterium to interact with algae. Notably, it possesses a large set of glycoside hydrolases and transporters, which may serve to process and assimilate algal metabolites. It also harbors several proteins likely to be involved in the synthesis of algal hormones such as auxins and cytokinins, as well as the vitamins pyridoxine, biotin, and thiamine. As of today, "Ca. P. ectocarpi" has not been successfully cultured, and identical 16S rDNA sequences have been found exclusively associated with Ectocarpus. However, related sequences (>= 97% identity) have also been detected free-living and in a Fucus vesiculosus microbiome barcoding project, indicating that the candidate genus "Phaeomarinobacter" may comprise several species, which may colonize different niches.