Caenorhabditis elegans must distinguish pathogens from nutritious food sources among the many bacteria to which it is exposed in its environment. We found that a single exposure to purified small RNAs isolated from pathogenic Pseudomonas aeruginosa (PA14) is sufficient to induce pathogen avoidance in the treated worms and in four subsequent generations of progeny. The RNA interference (RNAi) and PIWI-interacting RNA (piRNA) pathways, the germline and the ASI neuron are all required for avoidance behaviour induced by bacterial small RNAs, and for the transgenerational inheritance of this behavior. A single P. aeruginosa non-coding RNA, P11, is both necessary and sufficient to convey learned avoidance of PA14, and its C. elegans target, maco-1, is required for avoidance. Our results suggest that this non-coding-RNA-dependent mechanism evolved to survey the microbial environment of the worm, use this information to make appropriate behavioral decisions and pass this information on to its progeny.