Objective: To estimate health care utilization and costs incurred by homeless Veterans relative to nonhomeless Veterans and to examine the impact of a VA homelessness program on these outcomes. Data Sources/Study Setting: Combined Department of Veterans Affairs (VA) administrative and Medicare claims data. Study Design: Observational study using longitudinal data from Veterans engaged with the VA system and enrolled in Medicare. Veterans with administrative evidence of homelessness at any point during 2006–2010 were matched on period of military service to Veterans with no evidence of homelessness. Principal Findings: Experience of homelessness was associated with 1.37 (95 percent CI = 1.34–1.40) and 0.16 (95 percent CI = 0.14–0.17) more outpatient encounters per quarter in VA and non-VA settings, respectively, and 1.31 (95 percent CI = 1.30–1.32) and 0.49 (95 percent CI = 0.48–0.49) more inpatient days per quarter in VA and non-VA hospitals, respectively. These were associated with higher costs. Relative to stably housed Veterans less than 65 years of age, those enrolled in a VA homelessness program had 94.4 percent (95 percent CI = 90.7 percent–98.1 percent) more VA outpatient visits but 5.5 percent (95 percent CI = 3.0 percent–7.9 percent) fewer Medicare outpatient visits. Conclusions: Homelessness was associated with an increase in VA and Medicare utilization and cost. A VA homelessness program decreased use of Medicare outpatient services.