Objective: To investigate gender differences in beliefs about condom use among young, sexually active, heterosexual Australian adults. Design: Cross-sectional survey of 1,113 adults aged 18–26 years. Setting: Higher education institutions across New South Wales and Victoria, Australia. Method: Participants were recruited during higher-education orientation activities and asked to complete an anonymous survey. The survey captured beliefs about condom use and demographic data. Results: Although males were more likely than females to agree that their partners endorsed the consistent use of condoms, they were less likely to agree that their friends would support consistent condom usage. Males were also more likely to believe that condoms reduce sexual pleasure and give the impression that they are sexually promiscuous. Conclusion: Normalizing the purchase of condoms, repositioning condoms as erotic stimuli, and creating a supportive peer environment using peer-to-peer communication tools may bring about more positive perceptions regarding consistent condom use. Gender-specific safe sex campaigns should also be developed to address the different pattern of condom beliefs held by males and females.