Characterization of a nontraditional binding material containing cement kiln dust (CKD) and ground granulated blast furnace slag (GGBFS) is discussed in this paper. Significant compressive strength was obtained for a CKD–GGBFS blend with 70% CKD and 30% GGBFS at a water-to-binder ratio of 0.40 after 2 days of curing at elevated temperature. Similar strength was also obtained for the samples subjected to normal moisture curing over a period of 28 days. The compressive strength increased with additional moist curing in both the cases. The microstructural and the mineralogical examinations show that the strength development was mainly due to the formation of calcium silicate hydrate (C-S-H). In addition to normal C-S-H, aluminum and magnesium incorporated C-S-H phases were also present in the CKD–GGBFS blends. The formation of ettringite appears to be a contributing factor in early age strength development of CKD–GGBFS binder.