Despite early diagnosis and treatment, almost 20% of patients with early-stage (cT1-cT2N0) oral tongue squamous cell carcinoma (OTSCC) still die of their disease. The prognosis of OTSCC patients is influenced by several demographic, clinical, and histopathologic factors. The aim of this multicenter international study was to find which of the factors age, gender, stage, grade, lymphocytic host response, perineural invasion, worst pattern of invasion, or depth of invasion has the strongest prognostic power in early-stage OTSCC. Patient data of 479 patients with early-stage (cT1-2N0) OTSCC in Finland, Brazil, and the USA were retrieved and analyzed using Cox proportional hazards regression models. Our results indicate that depth of invasion (DOI) and worst pattern of invasion (WPOI) are the strongest pathological predictors for locoregional recurrence, with a hazard ratio (HR) for 4 mm DOI of 1.67 (95% confidence interval (CI) 1.07-2.60) and HR for WPOI of 1.46 (95% CI 0.95-2.25). In addition, mortality from early OTSCC was also predicted by DOI (HR 2.44, 95% CI 1.34-4.47) and by WPOI (HR 2.34, 95% CI 1.26-4.32). We suggest that clinically early-stage oral tongue carcinomas 4 mm or deeper, or with a growth pattern of small cell islands or satellites, should be considered as high-risk tumors which require multimodality treatment.