Between 1998 and 2007, 51,449 Gay Community Periodic Survey questionnaires were completed in Sydney, Melbourne and Brisbane, Australia. These included 23,424 where the respondents reported currently being in a relationship with a regular male partner. About 90% of men with a regular partner had been tested for HIV, and about three quarters had tested HIV-negative. Between 1998 and 2007 there was an increase in the proportion of men in HIV-negative seroconcordant relationships. About three quarters of men with a regular partner had negotiated an agreement about sex within their relationship. There was little change over time in the likelihood of having negotiated such agreements. There were, however, changes over time in the nature of these negotiated agreements: Over time, more men in HIV-discordant relationships permitted unprotected anal intercourse with their regular partners (P-trend < .001); among men in HIV-negative concordant relationships, an increasing proportion required a monogamous arrangement with their regular partner (P-trend < .001); and over time, fewer men in general required consistent condom use with casual partners (P-trend < .001). Some of these changes in negotiated agreements represent an increase in the potential risk of HIV transmission.