Background: Health literacy (HL) impacts medical care. We hypothesized that patients with low HL would have higher readmission rates following surgery. Methods: We conducted a prospective, multi-institutional study from 8/2015–6/2017 within the Veterans Affairs (VA) System including veterans who underwent general, vascular, or thoracic surgery. HL was assessed by Brief Health Literacy Screener and stratified into adequate vs. low. Patients were followed for 30 days post-discharge. Multivariable analyses examined correlations and logistic regression models adjusted for covariates. Results: 736 patients were enrolled in the study; 98% (n = 722) completed the HL survey. At discharge, 33.2% of patients had low HL. The overall 30-day readmission rate was 16.3%, with a significant difference by HL (Adequate HL: 13.3% vs. Low HL: 22.5%, p < 0.01). After adjusting for clinical and demographic covariates, patients with low HL were 59% more likely to be readmitted (OR = 1.59, 95% CI = 1.02–2.50). Conclusion: Low HL is common among VA surgery patients and is associated with readmission. Future studies should be focused on interventions to target this vulnerable patient population.