Obligate symbioses involving intracellular bacteria have transformed eukaryotic life, from providing aerobic respiration and photosynthesis to enabling colonization of previously inaccessible niches, such as feeding on xylem and phloem, and surviving in deep-sea hydrothermal vents. A major challenge in the study of obligate symbioses is to understand how they arise. Because the best studied obligate symbioses are ancient, it is especially challenging to identify early or intermediate stages. Here we report the discovery of a nascent obligate symbiosis in Howardula aoronymphium, a well-studied nematode parasite of Drosophila flies. We have found that H. aoronymphium and its sister species harbor a maternally inherited intracellular bacterial symbiont. We never find the symbiont in nematode-free flies, and virtually all nematodes in the field and the laboratory are infected. Treating nematodes with antibiotics causes a severe reduction in fly infection success. The association is recent, as more distantly related insect-parasitic tylenchid nematodes do not host these endosymbionts. We also report that the Howardula nematode symbiont is a member of a widespread monophyletic group of invertebrate host-associated microbes that has independently given rise to at least four obligate symbioses, one in nematodes and three in insects, and that is sister to Pectobacterium, a lineage of plant pathogenic bacteria. Comparative genomic analysis of this group, which we name Candidatus Symbiopectobacterium, shows signatures of genome erosion characteristic of early stages of symbiosis, with the Howardula symbiont’s genome containing over a thousand predicted pseudogenes, comprising a third of its genome.