Background: Since the discovery of the Malta fever agent, Brucella melitensis, in the 19th century, six terrestrial mammal-associated Brucella species were recognized over the next century. More recently the number of novel Brucella species has increased and among them, isolation of species B. pinnipedialis and B. ceti from marine mammals raised many questions about their origin as well as on the evolutionary history of the whole genus. Results: We report here on the first complete genome sequence of a Brucella strain isolated from marine mammals, Brucella pinnipedialis strain B2/94. A whole gene-based phylogenetic analysis shows that five main groups of host-associated Brucella species rapidly diverged from a likely free-living ancestor close to the recently isolated B. microti. However, this tree lacks the resolution required to resolve the order of divergence of those groups. Comparative analyses focusing on a) genome segments unshared between B. microti and B. pinnipedialis, b) gene deletion/fusion events and c) positions and numbers of Brucella specific IS711 elements in the available Brucella genomes provided enough information to propose a branching order for those five groups. Conclusions: In this study, it appears that the closest relatives of marine mammal Brucella sp. are B. ovis and Brucella sp. NVSL 07-0026 isolated from a baboon, followed by B. melitensis and B. abortus strains, and finally the group consisting of B. suis strains, including B. canis and the group consisting of the single B. neotomae species. We were not able, however, to resolve the order of divergence of the two latter groups.