This study quantified variation in key life-history traits of the widespread African mouth-brooding cichlid Pseudocrenilabrus multicolor victoriae. Egg size, number, batch reproductive effort, size at maturity and brooding efficiency were compared among field populations across a wide range of dissolved oxygen (DO) concentrations from extreme hypoxia to normoxia. In the laboratory, a similar suite of characters was quantified in F1 of low- and high-DO origin reared under low or high DO. In general, females from low-DO habitats and females reared under low DO were characterized by a smaller size at maturity and no difference in batch reproductive effort when compared with females from high-DO habitats or females reared under normoxia. A trade-off between egg size and number was evident in the field and in the laboratory-rearing experiment, but the direction of the trade-off differed. Egg size was negatively correlated with egg number across field populations; females collected from low-DO sites generally had more, smaller eggs relative to females from high-DO sites. In the laboratory-rearing experiment, F1 females of high-DO origin produced larger, fewer eggs than F1 females of low-DO origin, lending support to the field results and suggesting a heritable component to these traits. There was also an element of developmental plasticity, F1 females raised under low DO produced larger, fewer eggs compared with F1 females raised under high DO (regardless of population) suggesting that DO may interact with other variables to determine egg size in the field.