Timely use of contraception in the postpartum year is critical for pregnancy spacing, which protects a mother’s health and improves her ability to care for children. This qualitative study explored contraceptive decision-making among postpartum women in Nairobi, Kenya, with a focus on accounts of how women overcame barriers to postpartum contraceptive use. Focus groups (n = 61) and in-depth interviews (n = 30) explored experiences, barriers and actual use of postpartum contraception. Data were analysed using framework analysis, a method that organises qualitative data into themes and then interprets the data by mapping participant characteristics to these themes. Contraceptive use among women who desired future fertility was hindered by fear of side-effects and concern for partner disapproval. However, women who were satisfied with their family size more easily overcame these barriers. Tailoring postpartum contraceptive counselling to both assuage the concerns of women who desire future fertility and address the long-term contraceptive needs of mothers who desire to stop child-bearing could play a role in reducing the unmet need for contraception.