Human papillomavirus type 16 (HPV16) plays a role in the development of a subgroup of head and neck squamous cell carcinomas (HNSCC). However, uncertainty exists about the true impact of HPV in this tumor type as conflicting reports have been published with prevalence rates from 0 to 100%. We aimed to find a detection algorithm of a biologically and thus clinically meaningful infection, applicable for high-throughput screening of frozen and formalin-fixed paraffin embedded (FFPE) specimens. By considering detection of HPV E6 oncogene expression in frozen biopsies as gold standard for a meaningful HPV infection, the value of several assays was evaluated on FFPE tumor specimens and sera of 48 HNSCC patients. The following assays were evaluated on FFPE tissue samples: HPV DNA general primer (GP)5+/6+ PCR, viral load analysis, HPV16 DNA FISH detection, HPV16 E6 mRNA RT-PCR, p16 immunostaining, and on corresponding serum samples detection of antibodies against the HPV16 proteins L1, E6 and E7. Comparing single assays on FFPE tissue samples detection of E6 expression by RT-PCR was superior, but application remains at present limited to HPV16 detection. Most suitable algorithm with 100% sensitivity and specificity appeared p16 immunostaining followed by GP5+/6+ PCR on the p16-positive cases. We show that clinically meaningful viral HPV infections can be more reliably measured in FFPE HNSCC samples in a standard and high throughput manner, paving the way for prognostic and experimental vaccination studies, regarding not only HNSCC, but possibly also cancer types with HPV involvement in subgroups such as penile and anal cancer.