This study aimed to explore perceived determinants of condom use behaviors among male clients of female commercial sex workers (FCSWs) in Belu and Malaka districts, Indonesia. One-on-one in-depth interviews guided by the Health Belief Model (HBM) were used to collect the data from participants (n = 42). The Framework analysis for qualitative data was employed to analyze the data. Results demonstrated several factors associated with lack of and inconsistent condom use among the participants. They included self-perceived risk of contracting HIV infection, knowledge of the severity of HIV illness and its impacts, and condom use: its benefits and its influencing factors. Additionally, factors including reduced sexual pleasure and the lack of knowledge of how and where to access condoms were important perceived barriers to condom use among participants. Having seen images of HIV-/AIDS-positive people, knowing friends and relatives suffering from HIV, and knowing FCSWs as a high-risk group for HIV infection were the cues to using condoms among several participants. Likewise, self-efficacy was also associated with condom use behaviors among the participants. The findings indicate the needs for HIV/AIDS interventions that include dissemination of HIV/AIDS knowledge, condom promotion, and improvement in the availability of condoms for both FCSWs and their clients.