In this paper, I explore the optimal taxation of singles and couples in an economy with bargaining couples. The government is concerned with the redistribution of income from individuals with high utility to individuals with low utility, recognizing that some individuals live in couple households where resources are unevenly distributed. I analyze how redistributive linear income taxes, which depend on either gender or household composition (or both) impact the distribution of utility within and across households. An interesting implication arising from the interaction between the model elements is that even though between-group lump-sum transfers always favor women, when the bargaining power of men is high, women are subject to a higher tax rate; this in contrast to previous analyses of gender-based taxation. My quantitative analysis demonstrates that the welfare effects of gender-based taxation are sizable and even larger when taxes depend on the composition of the household.