Although patients with early-stage oral tongue squamous cell carcinoma (OTSCC) show better survival than those with advanced disease, there is still a number of early-stage cases who will suffer from recurrence, cancer-related mortality and worse overall survival. Incorporation of an immune descriptive factor in the staging system can aid in improving risk assessment of early OTSCC. A total of 290 cases of early-stage OTSCC re-classified according to the American Joint Committee on Cancer (AJCC 8) staging were included in this study. Scores of tumor-infiltrating lymphocytes (TILs) were divided as low or high and incorporated in TNM AJCC 8 to form our proposed TNM-Immune system. Using AJCC 8, there were no significant differences in survival between T1 and T2 tumors (p > 0.05). Our proposed TNM-Immune staging system allowed for significant discrimination in risk between tumors of T1N0M0-Immune vs. T2N0M0-Immune. The latter associated with a worse overall survival with hazard ratio (HR) of 2.87 (95% CI 1.92–4.28; p < 0.001); HR of 2.41 (95% CI 1.26–4.60; p = 0.008) for disease-specific survival; and HR of 1.97 (95% CI 1.13–3.43; p = 0.017) for disease-free survival. The TNM-Immune staging system showed a powerful ability to identify cases with worse survival. The immune response is an important player which can be assessed by evaluating TILs, and it can be implemented in the staging criteria of early OTSCC. TNM-Immune staging forms a step towards a more personalized classification of early OTSCC.