Food and/or housing instability (FHI) has been minimally examined in post-9/11 US veterans. A randomly selected nationally representative sample of men and women veterans (n = 38,633) from the post-9/11 US veteran population were mailed invitation letters to complete a survey on health and well-being. Principal component analysis and multivariable logistic regression were used to identify FHIs key constructs and correlates for 15,166 men and women respondents (9524 men, 5642 women). One-third of veterans reported FHI; it was significantly more likely among women than men (crude odds ratio = 1.31, 95% CI:1.21-1.41) and most prevalent post-service (64.2%). Mental Health/Stress/Trauma, Physical Health, and Substance Use were FHIs major constructs. In both sexes, significant adjusted associations (p < 0.01) were found between FHI and homelessness, depression, adverse childhood experiences, low social support, being enlisted, being non-deployed, living with seriously ill/disabled person(s), and living in dangerous neighborhoods. In men only, posttraumatic stress disorder (adjusted odds ratio (AOR) = 1.37, 95% CI:1.14-1.64), cholesterol level (elevated versus normal, AOR = 0.79, 95% CI:0.67-0.92), hypertension (AOR = 1.25, 95% CI:1.07-1.47), and illegal/street drug use (AOR = 1.28, 95% CI:1.10-1.49) were significant (p < 0.01). In women only, morbid obesity (AOR = 1.90, 95%CI:1.05-3.42) and diabetes (AOR = 1.53, 95% CI:1.06-2.20) were significant (p < 0.05). Interventions are needed that jointly target adverse food and housing, especially for post-9/11 veteran women and enlisted personnel.