Measles is a highly contagious infection that can cause severe illness in children. Vaccination is the primary means of controlling the infection, with elimination a possibility. However, the measles-containing vaccine coverage in sub-Saharan Africa (SSA) is 70% while that for Nigeria is 54% according to official estimates and 64.7% from household surveys. This review aims to identify factors that contribute to the poor coverage rate and proposes appropriate recommendations to address these factors. We conducted a comprehensive search of five databases (MEDLINE, Embase, Global Health, CINAHL Plus and PubMed) using the PICOTS (population, intervention, comparison, outcome, timing, study type) framework. The search was conducted in September 2017 in accordance with the Preferred Reporting Items for Systematic Reviews and Meta-Analyses guidelines and inclusion criteria were studies conducted in SSA, that evaluated measles vaccine coverage gaps, evaluated strategies for improving measles vaccination coverage and were published in English. The database search yielded 23 publications. Several different factors influencing measles vaccine coverage were identified and were grouped into four main areas: immunization system, information and communication, family characteristics and parental attitudes and knowledge. Fears and misconceptions were common reasons for non-vaccination. Activities to improve vaccination coverage were identified, including structural reforms such as siting health centres within or proximal to target communities, improving female literacy and conducting measles vaccination campaigns. Multiple reasons for poor measles vaccination coverage were identified. Factors influencing the immunization system and information and communication factors can be fixed at the country level, but challenges relating to family characteristics and parental attitudes and knowledge require solutions adapted to the community of concern. However, vaccination campaigns are an effective means of improving vaccination coverage and they reduce geographic and socio-economic inequities.