Head and neck cancer (HNC) is the seventh most common cancer worldwide, with a 5-year overall survival of 50-60%. Despite known survival factors, unexpected deaths underscore the need to refine pre-treatment survival predictions. This study aimed to identify novel data-driven HNC patient phenotypes, associated features and predict overall survival using deep survival clustering model VaDeSC. We used a retrospective cohort of 1341 HNC patients from Helsinki University Hospital, utilizing their pre-treatment clinical and demographic data from electronic health records. We identified six previously unrecognized HNC phenotypes with distinct survival patterns, highlighting the significance of BMI, sleep apnoea, TNM stage, tumour site, treatment intention, gender, and age-related treatment modalities. VaDeSC demonstrated strong predictive accuracy, clustering performance and generalizability, achieving C-index of 0.895 ± 0.015 on training and 0.782 ± 0.013 on test data. The phenotype purity was 0.102 ± 0.11 on training-validation data and 0.143 ± 0.006 on test data. Our findings demonstrated that clustering pre-treatment clinical survival data offers intuitively interpretable results with accurate individualised predictions. This approach holds significant potential for novel phenotype discovery across various diseases and endpoints.