Several Trichonympha protist species in the termite gut have independently acquired Desulfovibrio ectosymbionts in apparently different stages of symbiosis. Here, we obtained the near-complete genome sequence of Desulfovibrio phylotype ZnDsv-02, which attaches to the surface of Trichonympha collaris cells, and compared it with a previously obtained genome sequence of 'Candidatus Desulfovibrio trichonymphae' phylotype Rs-N31, which is almost completely embedded in the cytoplasm of Trichonympha agilis. Single-nucleotide polymorphism analysis indicated that although Rs-N31 is almost clonal, the ZnDsv-02 population on a single host cell is heterogeneous. Despite these differences, the genome of ZnDsv-02 has been reduced to 1.6 Mb, which is comparable to that of Rs-N31 (1.4 Mb), but unlike other known ectosymbionts of protists with a genome similar in size to their free-living relatives. Except for the presence of a lactate utilization pathway, cell-adhesion components and anti-phage defense systems in ZnDsv-02, the overall gene-loss pattern between the two genomes is very similar, including the loss of genes responsive to environmental changes. Our study suggests that genome reduction can occur in ectosymbionts, even when they can be transmitted horizontally and obtain genes via lateral transfer, and that the symbiont genome size depends heavily on their role in the symbiotic system.