The process children go through when learning about gender roles is an essential part of their knowledge construction. This acquired knowledge helps them learn about their roles in society. However, problems occur when children are presented with stereotypical constructions of masculinity and femininity that may inhibit their development. Thus, children's literature must be evaluated to uncover gendered messages. While overtly sexist messages in children's stories can be easily identified, the more subtle nuances of language require careful analysis. This paper begins by stressing the urgent need to evaluate Malaysian children's literature published in the English language. By distinguishing between ''overt'' and ''covert'' sexism in children's literature, we argue that the role of language in messages about gender identity in children's literature must be emphasised. Based on a selection of Malaysian children's literature, we attempt an analysis of lexical items that construct gender roles and identities, and we use computer- based programmes to reveal how power relations are established between males and females.