Transgender veterans are more likely than non-transgender (i.e., cisgender) veterans to experience housing instability, and they may experience unique challenges in accessing permanent supportive housing (PSH). The objective of this study was to explore transgender and cisgender veterans’ experiences utilizing PSH through the U.S. Departments of Housing and Urban Development-Veterans Affairs Supportive Housing (HUD-VASH) program. Between February and May 2018, 48 veterans (14 cisgender women, 17 cisgender men, 17 transgender individuals) completed an audio-recorded, semi-structured telephone interviews; all transgender individuals self-identified as transgender women. We used rapid identification of themes from audio recordings (RITA) to analyze the data. Half of the participants had been in HUD-VASH one to three years. Most respondents cited their case manager as a key facilitator in successfully becoming housed and identified lack of understanding the HUD-VASH admission processes and wait times as common barriers to housing. Other challenges included veterans’ inability to receive services until they were homeless and landlords’ reluctance to rent to veterans with histories of substance use. Transgender women veterans conveyed unique challenges related to sex-specific shelter experiences and incongruence of identification cards and gender expression.