Wolbachia are well known as bacterial symbionts of arthropods, where they are reproductive parasites, but have also been described from nematode hosts, where the symbiotic interaction has features of mutualism. The majority of arthropod Wolbachia belong to clades A and B, while nematode Wolbachia mostly belong to clades C and D, but these relationships have been based on analysis of a small number of genes. To investigate the evolution and relationships of Wolbachia symbionts we have sequenced over 70 kb of the genome of wOvo, a Wolbachia from the human-parasitic nematode Onchocerca volvulus, and compared the genes identified to orthologues in other sequenced Wolbachia genomes. In comparisons of conserved local synteny, we find that wBm, from the nematode Brugia malayi, and wMel, from Drosophila melanogaster, are more similar to each other than either is to wOvo. Phylogenetic analysis of the protein-coding and ribosomal RNA genes on the sequenced fragments supports reciprocal monophyly of nematode and arthropod Wolbachia. The nematode Wolbachia did not arise from within the A clade of arthropod Wolbachia, and the root of the Wolbachia clade lies between the nematode and arthropod symbionts. Using the wOvo sequence, we identified a lateral transfer event whereby segments of the Wolbachia genome were inserted into the Onchocerca nuclear genome. This event predated the separation of the human parasite O. volvulus from its cattle-parasitic sister species, O. ochengi. The long association between filarial nematodes and Wolbachia symbionts may permit more frequent genetic exchange between their genomes.