Connecting veterans with employment services can address housing instability. This paper describes barriers to implementation of employment services within the US Department of Veterans Affairs (VA) Health Care for Homeless Veterans (HCHV) program and identifies strategies for improving implementation efforts. We conducted qualitative telephone interviews with HCHV Employment Specialists (N= 16) between December 2019 and March 2020 and analyzed transcripts using a template analysis approach and aligned identified barriers within the domains of the Consolidated Framework for Implementation Research (CFIR) with implementation strategies established through the Expert Recommendations for Implementing Change (ERIC) project using the CFIR-ERIC Implementation Strategy Matching Tool. Barriers within the intervention’s characteristics consist of its complexity and a lack of evidence-based practices. Inner setting barriers include insufficient resources to support service provision and a lack of knowledge, information, and feedback. Outer setting barriers include inadequate resources to respond to veterans’ needs, transportation limitations, and employer hiring practices. Within characteristics of providers, a lack of self-efficacy and satisfaction with organizational commitment serve as barriers. Finally, ineffective strategies to engage veterans and employers and insufficient feedback about the progress and quality of implementation act as process barriers. ERIC strategies to overcome these barriers fall into four categories: identify champions and build coalitions, formalize implementation efforts, improve education and training opportunities, and develop approaches to better implement services at new locations. Identified barriers and strategies can inform vocational development services provided through both HCHV Employment Specialists and other providers to support better employment, housing, and health outcomes among participants.