This paper has analyzed the challenges of sustainability and scalability of HIS. The empirical analysis was conducted in a backward and disadvantaged region of Ethiopia. An ongoing process of HISP (Health Information System Program) was addressed and the main challenges in the implementation of sustainable and scalable district-based health information system in the context of Primary Health Care (PHC) sector in Ethiopia were identified. Human resource, infrastructure, and HIS related problems are the main challenges hindering the implementation of sustainable and scalable district-based health information systems in the region.