This article is based on data generated in an ethnographic study of gender in a Swedish preschool. Drawing on Judith Butler's understanding of performativity and (un)doing of gender, a new theoretical concept, "situated decoding of gender," is further developed by showing how the material and spatial dimension of the educational practice and the teachers' actions contribute to establishing and maintaining this process in an early childhood educational setting. Instead of normalising the gender binary, a reverse process occurs that turns what is perceived as feminine or masculine into a gender decoded state in which gender is made less relevant, or even irrelevant. It is argued that this continuous reiterative process emerges and is maintained by three main factors: (a) the preschool's physical environment, (b) the regular and repetitive structure of the educational practice and (c) the consistent actions of the teachers in the everyday practice.