Stress fractures are common in military personnel and endurance athletes, and nonsteroidal anti-inflammatory drug (NSAID) use is widespread in these populations. NSAIDs inhibit prostaglandin synthesis, which blunts the anabolic response of bone to physical activity and could therefore increase risk of stress fracture. The objective of this study was to determine whether prescribed NSAIDs were associated with stress fracture diagnoses among US Army soldiers. We also aimed to establish whether acetaminophen, an analgesic alternative to NSAIDs, was associated with stress fracture risk. A nested case-control study was conducted using data from the Total Army Injury and Health Outcomes Database from 2002 to 2011 (n = 1,260,168). We identified soldiers with a diagnosis of stress fracture (n = 24,146) and selected 4 controls per case matched on length of military service (n = 96,584). We identified NSAID and acetaminophen prescriptions 180 to 30 days before injury (or match date). We also identified soldiers who participated in basic combat training (BCT), a 10-week period of heightened physical activity at the onset of Army service. Among these individuals, we identified 9088 cases and 36,878 matched controls. Conditional logistic regression was used to calculate incident rate ratios (RR) for stress fracture with adjustment for sex. NSAID prescription was associated with a 2.9-fold increase (RR = 2.9, 95% confidence interval [CI] 2.8-2.9) and acetaminophen prescription with a 2.1-fold increase (RR = 2.1, 95% CI 2.0-2.2) in stress fracture risk within the total Army population. The risk was more than 5-fold greater in soldiers prescribed NSAIDs (RR = 5.3, 95% CI 4.9-5.7) and more than 4-fold greater in soldiers prescribed acetaminophen (RR = 4.4, 95% CI 3.9-4.9) during BCT. Our results reveal an association between NSAID and acetaminophen prescriptions and stress fracture risk, particularly during periods of heightened physical activity. Prospective observational studies and randomized controlled trials are needed to support these findings before clinical recommendations can be made. © 2018 American Society for Bone and Mineral Research.