Once-daily Truvada (Emtricitabine/Tenofovir) as a method of pre-exposure prophylaxis (PrEP) is one of the most promising biomedical interventions to eliminate new HIV infections; however, uptake among gay, bisexual, and other men who have sex with men has been slow amidst growing concern in popular/social media that PrEP use will result in reduced condom use (i.e., risk compensation). We investigated demographic, behavioral, and psychosocial differences in willingness to use PrEP as well as the perceived impact of PrEP on participants’ condom use in a sample of 206 highly sexually active HIV-negative gay and bisexual men. Nearly half (46.1%) said they would be willing to take PrEP if it were provided at no cost. Although men willing to take PrEP (vs. others) reported similar numbers of recent casual male partners (< 6 weeks), they had higher odds of recent receptive condomless anal sex (CAS)—i.e., those already at high risk of contracting HIV were more willing to take PrEP. Neither age, race/ethnicity, nor income were associated with willingness to take PrEP, suggesting equal acceptability among subpopulations that are experiencing disparities in HIV incidence. There was limited evidence to suggest men would risk compensate. Only 10% of men who had not engaged in recent CAS felt that PrEP would result in them starting to have CAS. Men who had not tested for HIV recently were also significantly more likely than others to indicate willingness to take PrEP. Offering PrEP to men who test infrequently may serve to engage them more in routine HIV/STI testing and create a continued dialogue around sexual health between patient and provider in order to prevent HIV infection.