Microbial symbionts of multicellular hosts originate from free-living ancestors and often persist through vertical transmission, but their mechanisms of establishment are not well understood. Here, we studied acquisition and transmission routes in a nascent symbiosis involving the bacterium Sodalis praecaptivus subsp. spalangiae (Sodalis SC) and the parasitoid wasp Spalangia cameroni. Using fluorescence in situ hybridization, transmission electron microscopy, and experimental infections, we found that oocytes are devoid of Sodalis SC, but the female venom gland is densely colonized. Sodalis SC is injected with the venom into the fly host, subsequently acquired by larval progeny during feeding, invades through the larval gut epithelium into multiple host organs, and eventually localizes in the venom gland. Adult wasps can also acquire Sodalis SC by artificial feeding, but, in this case, the bacterium is not transmitted vertically. Additionally, Sodalis SC is localized in the testes of some males, transmitted paternally at low frequency, and females that inherit Sodalis SC paternally can subsequently transmit it via the venom. To assess the specificity of the symbiosis, we performed experiments with the closely related free-living species Sodalis praecaptivus subsp. praecaptivus (Sodalis PP), known to initiate symbiosis with other insects. Sodalis PP is readily acquired when supplied artificially to wasp larvae but not transmitted to wasp progeny, because it fails to proliferate in the parasitized host. Our results indicate that non-ovarian transmission routes of intracellular symbionts may be more common than currently appreciated and provide a scenario for the early steps in establishing persistent symbiotic associations in insects.