Low-Middle-Income-Countries (LMICs) are beginning to adopt national health data warehousing (NHDWs) for making strategic decisions and for improving health outcomes. Given the numerous challenges likely to be faced in establishment of NHDWs by LMICs, it is prudent that evaluations are done in relation to the data warehouses (DWs), in order to identify and mitigate critical issues that arise. When critic issues are not identified, DWs are prone to suboptimal implementation with compromised outcomes. Despite the fact that several publications exist on evaluating DWs, evaluations specific to health data warehouses are scanty, with almost none evaluating NHDWs more so in LMICs. This paper uses a systematic approach guided by an evaluation framework to identify critical issues to be considered in evaluating Kenya's NHDW.