The last decade has seen the expansion of trans identities that are gender queer, non-binary, androgynous, or multiply-sexed and gendered in Western Europe. These developments mark a shift from a uniformly gender-binaried system to one that encompasses some degree of gender pluralism, as reflected to an extent in policy changes in some European countries. However, gender binarism is still prevalent. This article uses the case of Norway to demonstrate a contrast between the citizenship statuses afforded to transsexual men and women, and the lack of citizenship rights that people with non-binary identities, and other gender-variant people who are not diagnosed as transsexual, face. The article addresses the historical role of the Norwegian state in perpetuating gender binaries, in key areas such as identity recognition. It then explores the ways in which Norwegian social policy is changing towards more trans-sensitive positions.