Research is limited about whether and to what extent registered sex offenders (RSOs) face an increased risk of housing instability. The intersection of RSO and housing instability is particularly salient for veterans as there are disproportionately higher rates of veterans among both RSOs and homeless populations. This study assessed the relationship between RSO status and risk of housing instability and homelessness among military veterans. We matched a list of 373,774 RSOs obtained from publicly available sex offender registries in 19 states with a cohort of 5.9 million veterans who responded to a brief screening for housing instability administered throughout the Veterans Health Administration between 2012 and 2016. Logistic regression estimated adjusted odds of any housing instability and homelessness among veterans identified as RSOs. Veterans identified as RSOs had 1.81 (95% confidence interval [CI] 1.46–2.25) and 2.97 (95% CI 1.67–5.17) times greater odds of reporting any housing instability and homelessness, respectively, than non-RSOs. Findings represent some of the strongest evidence to date for the high risk of housing instability and homelessness among RSOs, suggesting a clear gap in policy and programmatic responses to their unique housing needs. Evidence-based alternative approaches to residence restriction laws may reduce recidivism and protect public safety.