Objective: As women emerge as a significant segment of the Veteran population, there is a need to understand how they enter the homeless system, the impact of homelessness on healthcare, and how this varies by gender. Methods: This study provides a gender-based comparison of Veterans’ utilization of U.S. Department of Veterans Affairs (VA) health and behavioral health services following the onset of a homeless episode and assesses the relationship between services utilization and Veterans’ entry into the homeless system. Results: Male and female veterans were equally as likely to use mainstream and VA homeless services. There were few differences between genders in inpatient services use following a homeless episode. Men used more substance abuse outpatient treatment and emergency services whereas women used outpatient medical treatment. Veterans who sought non-VA homeless services were less likely to use outpatient services but more likely to access emergency services. Conclusion: Veterans experiencing homelessness who do not use VA homeless assistance services are less engaged with preventative VA health and behavioral healthcare. Veterans who are homeless but not identified as such by VA, particularly women, need additional engagement. Ongoing study of gender-based differences in services utilization among homeless and at-risk Veterans is needed.