Neutrophil extracellular traps (NETs) represent web-like structures consisting of externalized DNA decorated with granule proteins that are responsible for trapping and killing bacteria. However, undesirable effects of NET formation during carcinogenesis, such as metastasis support, have been described. In the present study, we evaluated the correlation between NETosis and disease progression in head and neck cancer (HNC) patients in order to establish a valid biomarker for an early detection and monitoring of HNC progression. Moreover, factors influencing NET release in HNC patients were revealed. We showed a significantly elevated vital NETosis in neutrophils isolated from early T1–T2 and N0–N2 stage patients, as compared to healthy controls. Additionally, in our experimental setting, we confirmed the involvement of tumor cells in the stimulation of NET formation. Interestingly, in advanced cancer stages (T3–4, N3) NETosis was reduced. This also correlated with the levels of granulocyte colony-stimulating factor (G-CSF) in plasma and tumor tissue. Altogether, we suggest that the elevated NETosis in blood can be used as a biomarker to detect early HNC and to predict patients at risk to develop tumor metastasis. Therapeutic disruption of NET formation may offer new roads for successful treatment of HNC patients in order to prevent metastasis.