Background: Epidemiological surveillance data indicate that a majority of HIV-infected in the United States (U.S.) military are African-Americans and men who have sex with men. There is limited research about barriers to HIV prevention among military service members and the unique factors that contribute to HIV stigma. Methods: A convenience sample of 30 U.S. service members were recruited from an infectious disease clinic. In depth interviews were conducted and data analyzed using a thematic coding process. Results: Two broad categories were identified: 1) Outcomes of HIV Stigma: Fear of Rejection, Shame, and Embarrassment; and 2) Strategies for combating stigma which include increasing HIV education and prevention resources. Military policies and institutional culture regarding sexuality were found to contribute to stigma. Conclusions: Participants identified a need for HIV education and suggested individuals living with HIV serve as mentors. A peer-to-peer intervention for delivering HIV prevention education may address these needs and reduce HIV stigma.