(1) Background: Sarcopenia lasting >1 year might be considered a chronic condition in many HNSCC patients. CT-scan-derived Skeletal Muscle Mass Index (SMI) is an established surrogate of sarcopenia; yet, the cut-off reported in the literature (literature-based, lb-SMI < 43.2) is mainly based on the risk of chemoradiotherapy-induced toxicity, and the optimal value to discriminate OS is under-investigated. (2) Methods: The effect on OS of the lb-SMI cutoff was compared with an untailored OS-oriented SMI cutoff obtained in a cohort of consecutive advanced HNSCC patients treated with primary chemoradiotherapy, bio-chemotherapy or chemo-immunotherapy (cohort-specific, cs-SMI cutoff). Gender- and BMI-tailored (gt-SMI and bt-SMI) cut-offs were also evaluated. Cutoff values were identified by using the maximally selected rank statistics for OS. (3) Results: In 115 HNSCC patients, the cs-SMI cutoff was 31.50, which was lower compared to the lb-SMI reported cut-off. The optimal cut-off separately determined in females, males, overweight and non-overweight patients were 46.02, 34.37, 27.32 and 34.73, respectively. gt-SMI categorization had the highest effect on survival (p < 0.0001); its prognostic value was independent of the treatment setting or the primary location and was retained in a multivariate cox-regression analysis for OS including other HNSCC-specific prognostic factors (p = 0.0004). (4) Conclusions: A tailored SMI assessment would improve clinical management of sarcopenia in chemoradiotherapy-, bio-chemotherapy- or chemo-immunotherapy-treated HNSCC patients. Gender-based SMI could be used for prognostication in HNSCC patients.