HIV transmission is common within MSM couples; despite recommendations that MSM who engage in risky sexual behaviors get tested biannually/annually, little is known about the testing patterns of MSM while in a current primary relationship. This study compared demographic and relationship characteristics of groups of MSM with different testing patterns while in their primary relationships, and assessed which factors were associated with regular or irregular testing. 275 HIV-negative male couples/550 MSM were recruited online to complete a survey in 2011. Since the start of their relationship, 21% of MSM tested for HIV every 3, 4, or 6 months; 29% tested once a year; 30% tested only when they felt at-risk for HIV; and 20% never tested for HIV. Bivariate analyses indicated men who had never been tested while in their relationship were younger, less educated, had greater trust in their partner, and were less likely to be in a couple that had one or both men having had sex with someone else. In the multivariate analyses, testing at regular intervals was associated with higher education, having a sexual agreement, being in a couple that had one or both men having had sex with someone else, and having lower faith in trust toward the main partner. Findings suggest that many MSM's testing behaviors while in their primary relationship do not align with their risk profile. Trust appears to be a barrier to regular HIV testing, which may be addressed by encouraging MSM to negotiate clear sexual agreements with their primary partner.