Messages that frame a target behavior in terms of its benefits (gain frame) or costs (loss frame) have been widely and successfully used for health promotion and risk reduction. However, the impact of framed messages on decisions to have sex and sexual risk, as well as moderators of these effects, has remained largely unexplored. We used a computerized laboratory task to test the effects of framed messages about condom use on young adults' sexual decision making. Participants (N = 127) listened to both gain- and loss-framed messages and rated their intentions to have sex with partners who posed a high and low risk for sexually transmitted infections (STIs). The effects of message frame, partner risk, participant gender, ability to adopt the messages, and message presentation order on intentions to have sex were examined. Intentions to have sex with high-risk partners significantly decreased after the loss-framed message, but not after the gain-framed message, and intentions to have sex increased for participants who received the gain-framed message first. Yet, participants found it easier to adopt the gain-framed message. Results suggest that loss-framed messages may be particularly effective in reducing intentions to have sex with partners who might pose a higher risk for STIs, and that message presentation order may alter the relative effectiveness of gain- and loss-framed messages on sexual decision making. Future studies should examine the precise conditions under which gain- and loss-framed messages can promote healthy sexual behaviors and reduce sexual risk behaviors.