Expectations that gender‐mainstreaming efforts would effectively advance gender equality have been disappointed in contemporary sub‐Saharan Africa. Examining this apparent disconnect, we focus on the narratives through which policy‐makers relate to, and dis/engage with, gender issues. Using in‐depth interviews and stakeholder meetings, our multi‐step analysis identifies story episodes from which we reconstruct stories and narratives. The analysis reveals a complex ecology of 22 stories, clustered in five main narratives. While most stories unfold a gender equality narrative, four competing narratives emerge. Shifts during conversations from the gender equality to other narratives reveal that the discursive engagement with gender mainstreaming is accompanied by simultaneous resistance, deconstruction and revocation. These narrative shifts exercise four distinct power effects: They (1) shift blame for ineffective gender implementation; (2) legitimize policy inaction; (3) foreground and naturalize patriarchy; and (4) promote the diversion of resources. The implicit communicative strategies exercise power through ideas (persuade listeners that the equality narrative is inappropriate), power over ideas (gender equality ideas are rejected or frustrated) and power in ideas (entrenched patriarchy ideas are reproduced). Attention to ideational power through policy narrative contributes to explain implementation issues with gender mainstreaming in Uganda, and is likely to be relevant beyond this case.