Background: The extent of preoperative opioid utilization and the relationship with pain-related readmissions are not well understood. Methods: VA Surgical Quality Improvement Program data on general, vascular, and orthopedic surgeries (2007–2014) were merged with pharmacy data to evaluate preoperative opioid use and pain-related readmissions. Opioid use in the 6-month preoperative period was categorized as none, infrequent, frequent, and daily. Results: In the six-month preoperative period, 65.7% had no opioid use, 16.7% had infrequent use, 6.3% frequent use, and 11.4% were daily opioid users. Adjusted odds of pain-related readmission were higher for opioid-exposed groups vs the opioid-naïve group: infrequent (OR 1.17; 95% CI:1.04–1.31), frequent (OR 1.28; 95% CI:1.08–1.52), and daily (OR 1.49; 95% CI:1.27–1.74). Among preoperative opioid users, those with a pain-related readmission had higher daily preoperative oral morphine equivalents (mean 44.5 vs. 36.1, p < 0.001). Conclusions: Patients using opioids preoperatively experienced higher rates of pain-related readmissions, which increased with frequency and dosage of opioid exposure.