The paper investigates the complex relationships between premarital fertility and HIV/AIDS in sub-Saharan African countries. The DHS surveys provided data to compute the prevalence of premarital fertility, defined as any birth before the first marriage. The UNAIDS database provided data to compute the prevalence of HIV infection among pregnant women. Results indicate a moderate association between the prevalence of premarital fertility and the prevalence of HIV infection (correlation coefficient = 0.64, P< 0.0001), and similar geographical patterns. Compared with the average pattern, outlier countries had either high levels of premarital fertility and relatively low HIV prevalence (Liberia, Madagascar, Gabon, Congo), or high levels of HIV prevalence despite low levels of premarital fertility (Lesotho, Malawi, Zambia, Zimbabwe). The overall relationship is discussed in light of the relationships between age at marriage, permissiveness and lack of protection during intercourse and their impact on premarital fertility and HIV infection among women.