Head and neck squamous cell carcinoma (HNSCC) is the sixth most common cancer in the world and has not seen improved survival rates over the past few decades. Current treatment plans include surgery, radiation therapy, and chemotherapy, but these are relatively ineffective options for recurrent or metastatic tumors. Therefore, there is a high priority for new therapies that specifically target the resistant HNSCC cancer stem cells (CSCs), a subpopulation responsible for tumor initiation and metastasis. Given their vast effects on gene expression and biological processes, including stem cell capabilities, non-coding RNAs (ncRNAs) have become a promising new repertoire of genes to investigate as potential diagnostic or therapeutic targets. This review presents a comprehensive overview of current investigative studies that can contribute to our understanding of the still tentative link between ncRNA and the biology of HNSCC cancer stem cells. In doing so, we aim to analyze the potential role of stem cell-related ncRNAs in the development of molecularly targeted cancer therapy for HNSCC. Although the majority of updated knowledge on HNSCC and ncRNA focuses heavily on microRNA, we chose to give considerable attention to the promise of other classes of ncRNAs (lncRNA, piRNA, and snoRNA), many of which are not yet well characterized or are yet to be discovered, and thus represent a potentially exciting and untapped pool of molecular targets or biomarkers in HNSCC therapy.