Competing needs pose barriers to engagement in HIV medical care. Mixed methods were used to explore and describe the needs of participants enrolled in Access to Care, a national HIV linkage, retention and re-engagement in care (LRC) program that served people living with HIV who knew their status but were not engaged in care. When asked to prioritize their most urgent needs, participants reported housing or shelter (31%), HIV medical services (24%), and employment (8%). When we assessed the HIV continuum of care by needs status, we found no significant differences in linkage, retention, or viral suppression between participants with and without basic needs. Qualitative interviews with program staff contextualized the barriers to HIV medical care faced by participants and explored the strategies used by LRC programs to address participant needs. Study findings will be of use to future programs and have implications for HIV policy, in particular the implementation of the National HIV/AIDS Strategy (2015–2020).