The emergence of immune checkpoint inhibitors (ICIs) has revolutionized the treatment of recurrent/metastatic (R/M) head and neck squamous cell carcinoma (HNSCC). Biomarkers of the therapeutic efficacy of ICIs have been extensively investigated. In this study, we aimed to analyze whether molecular phenotypes of circulating tumor cells (CTCs) are associated with treatment responses and clinical outcomes in patients with R/M HNSCC treated with nivolumab. Peripheral blood samples were collected before treatment initiation and after four infusions of nivolumab. CTCs isolated by depletion of CD45-positive cells were analyzed to determine the expression of EPCAM, MET, KRT19, and EGFR using real-time quantitative polymerase chain reaction. CTC-positive samples were analyzed to determine the expression of PIK3CA, CCND1, SNAI1, VIM, ZEB2, CD44, NANOG, ALDH1A1, CD47, CD274, and PDCD1LG2. Of 30 patients treated with nivolumab, 28 (93.3%) were positive for CTCs. In 20 CTC-positive patients, molecular alterations in CTCs before and after nivolumab treatment were investigated. Patients with MET-positive CTCs had significantly shorter overall survival than those with MET-negative CTCs (p = 0.027). The expression level of CCND1 in CTCs of disease-controlled patients was significantly higher than that of disease-progressed patients (p = 0.034). In disease-controlled patients, the expression level of CCND1 in CTCs significantly decreased after nivolumab treatment (p = 0.043). The NANOG expression in CTCs was significantly increased in disease-controlled patients after nivolumab treatment (p = 0.036). Our findings suggest that the molecular profiling of CTCs is a promising tool to predict the treatment efficacy of nivolumab.