Background The World Health Organization recommends HIV testing is included in routine screening tests for all pregnant women in order to prevent mother-to-child-transmission of HIV and reduce maternal morbidity and mortality. Objectives To assess the proportion of women approached and tested for HIV at delivery and factors associated with non-testing at the maternity ward of the Simão Mendes National Hospital (HNSM) in Bissau, Guinea-Bissau. Methods We conducted a retrospective cross-sectional study among women presenting for delivery from June 2008 until May 2013. During the study period, national policy included opt-out HIV-testing at delivery. Modified Poisson regression models were used to examine the association of maternal characteristics with HIV testing. Time trends were determined using Pearson’s χ2 test. Results Seventy-seven percent (24,217/31,443) of women presenting for delivery were counselled regarding PMTCT, of whom 99.6% (24,107/24,217) proceeded with HIV testing. The provision of opt-out HIV testing at labour increased from 38.1% (1,514/3973) in 2008 to 95.7% (2,021/2,113) in 2013, p<0.001. There were four distinct periods (two or more consecutive calendar months) when less than 50% of women delivering at HNSM were tested. Periods of political instability were significantly associated with not testing for HIV (adjusted prevalence ratio [APR] 1.79; 95% CI 1.73–1.84), as was a lower educational status (APR 1.05; 95% CI 1.00–1.10), admission during evenings/nights (APR 1.05; 95% CI 1.01–1.09) and on Sundays (APR 1.14; 95% CI 1.07–1.22) and Mondays (APR 1.12; 95% CI 1.05–1.19). Conclusions Rapid scale-up of PMTCT HIV testing services and high testing coverage was possible in this resource-limited setting but suffered from regular interruptions, most likely because of test stock-outs. Establishing proper stock management systems and back-up plans for periods of political instability is required to ensure the maintenance of health system core functions and increase health system resilience.