Sexuality is a fluid entity, defined by certain historical period, space and time. As a discourse, the power/knowledge relations determine the definition of sex. This research revealed on how the sexuality is understood and constructed in Indonesian context by the different regimes: New Order and Post New Order. Both regimes were controlled by the different groups, in different political, social and cultural contexts, and resulted the different discourses of sex. Hai magazine becomes the relevant object of this research to understand sexuality as the arena of power/knowledge practice. This research-using Norman Fairclough’s Critical Discourse Analysis-also focused on the articles and rubrics of sexuality, which published during 1995-2004 as the analyzed texts. From the analysis of text, discursive and social practice, this research explained that Hai constructed the ambivalence discourse of sexuality. The discourse of male sexuality produced in Hai magazine becomes the compromise of the sexual conservatism and sexual liberalism.