Parental exposure to pathogens can prime offspring immunity in diverse organisms. The mechanisms by which this heritable priming occurs are largely unknown. Here we report that the soil bacteria Pseudomonas vranovensis is a natural pathogen of the nematode Caenorhabditis elegans and that parental exposure of animals to P. vranovensis promotes offspring resistance to infection. Furthermore, we demonstrate a multigenerational enhancement of progeny survival when three consecutive generations of animals are exposed to P. vranovensis. By investigating the mechanisms by which animals heritably adapt to P. vranovensis infection, we found that parental infection by P. vranovensis results in increased expression of the cysteine synthases cysl-1 and cysl-2 and the regulator of hypoxia inducible factor rhy-1 in progeny, and that these three genes are required for adaptation to P. vranovensis. These observations establish a CYSL-1, CYSL-2, and RHY-1 dependent mechanism by which animals heritably adapt to infection.