Gastric cancer (GC) stem cells (GCSCs) are characterized as high level of ALDH activity, however, the mechanisms of maintenance of high ALDH activity and stemness in GCSCs are largely unknown. Here, we report that KDM4C, a H3K9me2/3-demethylase, epigenetically regulates ALDH1A3 by histone demethylation and forms a feed-forward loop with ALDH1A3 to supports GS stemness. Ectopic expression of both KDM4C and ALDH1A3 promotes the properties of GCSCs, including spherogenecity, self-renewal, CD44 expression and ALDH activity; knockdown of anyone abolished the effect of each other. KDM4C directly binds to the promoter of ALDH1A3, leads to histone demethylation, thereby promoting ALDH1A3 transcription. Upregulated ALDH1A3 in turn transcriptionally upregulates KDM4C. Simultaneous inhibition of KDM4C and ALDH1A3 synergistically sensitizes GC sphere-derived cells to traditional chemotherapeutic drugs. The finding that upregulated ALDH1A3 promotes its own transcription via KDM4C-mediated epigenetic modification represents an important feed-forward mechanism for GCSCs to maintain stemness and promote tumourigenesis and our work thus suggests a novel therapeutic strategy for eradicating human GCSCs. To investigate the mechanisms underlying KDM4C promoting CG stemness, we identified the differentially expressed proteins (DEPs) between KDM4C-overexpressing and control AGS cells by iTRAQ-based quantitative proteomic analysis.