When viewed over time, many gay men's relationships are not static, or firmly fixed to monogamy or non-monogamy. This paper uses in-depth interviews with 61 Australian gay men to explore how monogamy and non-monogamy are experienced over time, expectations of what constitutes the norms regarding gay men's relationships and how couples experience and practices change. Although some gay men may idealise monogamy, particularly at the beginning of a relationship, it is often experienced as temporary. Non-monogamy is often seen as a likely prospect for gay relationships owing to the social and cultural norms that operate in gay communities. These expected trajectories are reflected in practice - many relationships begin monogamously and then become non-monogamous over time. While the application of 'rules', experimentation and flexibility can facilitate change, couples may struggle to navigate new territory as their relationship structures shift. This is particularly the case when partners value monogamy and non-monogamy differently, or when one partner's values change. These findings shed light on how gay men approach change to the status of 'fidelity' within their relationships, and the tensions and opportunities that change can produce for couples.