Gender analysts have long recognised that challenging existing patriarchal structures involves risks for women, who may lose both long-term support and protection from kin. However, understanding the specific ways in which they ‘bargain with patriarchy’ in particular contexts is relatively poorly understood. We focus on a Mijikenda fishing community in coastal Kenya to explore contradictions in gendered power relations and how women deploy these to reinterpret gendered practices without directly challenging local patriarchal structures. We argue that a more complex understanding of women’s creative agency can reveal both the value to women of culturally-specific gendered roles and responsibilities and the importance of subtle changes that they are able to negotiate in these. With reference to food provisioning, the analysis contributes to more nuanced understandings of gendered household food security and women’s creative approaches to maintaining long-term security in their lives.