Background: Wolbachia are among the most abundant symbiotic microbes on earth; they are present in about 66% of all insect species, some spiders, mites and crustaceans, and most filarial nematode species. Infected filarial nematodes, including many pathogens of medical and veterinary importance, depend on Wolbachia for proper development and survival. The mechanisms behind this interdependence are not understood. Interestingly, a minority of filarial species examined to date are naturally Wolbachia-free. Methodology/Principal Findings: We used 454 pyrosequencing to survey the genomes of two distantly related Wolbachia- free filarial species, Acanthocheilonema viteae and Onchocerca flexuosa. This screen identified 49 Wolbachia-like DNA sequences in A. viteae and 114 in O. flexuosa. qRT-PCR reactions detected expression of 30 Wolbachia-like sequences in A. viteae and 56 in O. flexuosa. Approximately half of these appear to be transcribed from pseudogenes. In situ hybridization showed that two of these pseudogene transcripts were specifically expressed in developing embryos and testes of both species. Conclusions/Significance: These results strongly suggest that the last common ancestor of extant filarial nematodes was infected with Wolbachia and that this former endosymbiont contributed to their genome evolution. Horizontally transferred Wolbachia DNA may explain the ability of some filarial species to live and reproduce without the endosymbiont while other species cannot.