Despite national plans and policies to reduce HIV infection rates in the nation, Penang remains a state with a high HIV infection rate within the gay male population. This research therefore, undertook to discover and analyse challenges of condom use faced by gay men in Penang. The research took the qualitative route of research design and collected data utilising the purposive method and snowball technique. Respondents were interviewed in-depth utilising a semi-structured questionnaire and 33 respondents were gathered until the point of data saturation was achieved. Data were analysed using a content analysis matrix and all data were secured via 128-bit encryption. The research gained clearance to proceed from the Ethics Committee of Universiti Sains Malaysia. Despite assertions of assertiveness and confidence in negotiating safer sex with sexual partners, the findings showed that respondents faced a myriad of challenges to negotiating condom use, as well as erratic condom use. The findings also showed that the respondents discarded safer sex when sexual desire was strong, that they had multiple sexual partners and had reservations when inquiring about the sexual history and HIV status of their sexual partners. However, there were no findings to indicate that the respondents discarded safer sex practices due to the availability of highly active antiretroviral therapy (HAART) or while under the influence of recreational drugs. Although the respondents recognised the value of practicing safer sex, there exists a disjoint between the intent to practicing safer sex and the actual execution. Personal choices derail the intent to practicing safer sex and signalling a need for an individualised approach to overcoming challenges to safer sex. Challenges to the practice of safer sex come in various forms and need to be addressed via an individualised approach. National policy is vital to the reduction of HIV infection rates. Cognizance of how gay men make their safer sex choices is equally vital in this endeavour. Implications of the findings for policy development and future research are discussed.