Nitric oxide (NO) is released into the air by NO-producing organisms; however, it is unclear if animals utilize NO as a sensory cue. We show that C. elegans avoids Pseudomonas aeruginosa (PA14) in part by detecting PA14-produced NO. PA14 mutants deficient for NO production fail to elicit avoidance and NO donors repel worms. PA14 and NO avoidance are mediated by a chemosensory neuron (ASJ) and these responses require receptor guanylate cyclases and cyclic nucleotide gated ion channels. ASJ exhibits calcium increases at both the onset and removal of NO. These NO-evoked ON and OFF calcium transients are affected by a redox sensing protein, TRX-1/thioredoxin. TRX-1's trans-nitrosylation activity inhibits the ON transient whereas TRX-1's de-nitrosylation activity promotes the OFF transient. Thus, C. elegans exploits bacterially produced NO as a cue to mediate avoidance and TRX-1 endows ASJ with a bi-phasic response to NO exposure.