Men who have sex with men (MSM) are at high risk for acquiring HIV in Belgium. This study explores MSMs’ hypothetical willingness to use pre-exposure prophylaxis (PrEP), assesses it against formal PrEP eligibility criteria, and identifies factors associated with incongruence between eligibility and willingness. We used data from an online survey of n = 1444 self-reported HIV-negative MSM. Participants were recruited through social media of MSM organizations and dating apps. Univariate analysis described PrEP willingness and eligibility; bivariate analyses examined how specific co-variates (socio-demographic, knowledge-related, and attitudinal and behavioral factors) were associated with eligibility and willingness. About 44% were eligible for PrEP and about 70% were willing to use it. Those who were eligible were significantly more likely be willing to take PrEP (p < 0.001). Two incongruent groups emerged: 16% of eligible participants were unwilling and 58% of ineligible participants were willing to use PrEP. Factors associated with this incongruence were sexual risk behavior, HIV risk perception, partner status, PrEP knowledge, and attitudinal factors. Because the two groups differ in terms of profiles, it is important to tailor HIV prevention and sexual health promotion to their needs. Among those at risk but not willing to take PrEP, misconceptions about PrEP, and adequate risk perception should be addressed.