Recent decades of improvements to routine health information systems in low- and middle-income countries (LMICs) have increased the volume of health data collected. However, countries continue to face several challenges with quality production and use of information for decision-making at sub-national levels, limiting the value of health information for policy, planning and research. Improving the quality of data production and information use is thus a priority in many LMICs to improve decision-making and health outcomes. This qualitative study identified the challenges of producing and using routine health information in Western Province, Zambia. We analysed the interview responses from 37 health and social sector professionals at the national, provincial, district and facility levels to understand the barriers to using data from the Zambian health management information system (HMIS). Respondents raised several challenges that we categorized into four themes: governance and health system organization, geographic barriers, technical and procedural barriers, and challenges with human resource capacity and staff training. Staff at the facility and district levels were arguably the most impacted by these barriers as they are responsible for much of the labour to collect and report routine data. However, facility and district staff had the least authority and ability to mitigate the barriers to data production and information use. Expectations for information use should therefore be clearly outlined for each level of the health system. Further research is needed to understand to what extent the available HMIS data address the needs and purposes of the staff at facilities and districts.