Purpose: Characteristics associated with having a primary care provider (PCP), patient–provider trust, and sexual behavior disclosure were examined among men who have sex with men (MSM). Methods: MSM ( N = 4239) were surveyed regarding demographic, behavioral, and medical characteristics. Multivariable logistic regression analyses were used. Results: Among 86.3% of MSM with a PCP, characteristics associated with lower patient–provider trust included younger age, Asian, bisexual, HIV-negative-not-on-pre-exposure prophylaxis, HIV-unknown, and lower medical literacy; with nondisclosure: Asian, bisexual, straight, HIV-negative, HIV-unknown, fewer partners, recruitment source, lower medical literacy, and lower patient–provider trust. Conclusion: Medical literacy and patient–provider trust are promising points of intervention to improve health outcomes among MSM.