The effect of nitrogen additions on fatigue behavior has been examined in near-equiaxed, rolled Ti-6Al-4V bar. This is the first-time nitrogen content that has been systematically explored with respect to monotonic and cyclic properties in a Ti-6Al-4V alloy base composition. Nitrogen additions were found to increase the β-transus temperature and strength, but they decreased ductility, even in microstructures where some β phase remained. This carried across into both the low- and high cycle fatigue behavior; even small contents of 240 and 560 ppmwN caused reductions in both low cycle fatigue life and high cycle fatigue strength. In samples containing 240 and 560 ppmwN, a conventional striated fractographic appearance was observed, but a dramatic change to a macroscopically brittle fracture surface was observed at 1800 and 3600 ppmwN, but still with substantial evidence of plasticity at the microscale. Therefore, neither microstructure or fractographic examination, nor EDX-based compositional analysis in the electron microscope are necessarily a reliable indicator of an absence of deleterious nitrogen contamination. This is significant for the investigation of potentially nitrogen-contaminated surface-initiated cracks, either due to service or processing exposures.