Understanding the specific geographical distribution of stunting is essential for planning and implementing targeted public health interventions in high-burdened countries. This study investigated geographical variations in the prevalence of stunting sub-nationally, and the determinants of stunting among children under 5 years of age in Ethiopia. We used the 2016 Ethiopia Demographic and Health Survey (EDHS) dataset for children aged 0–59 months with valid anthropometric measurements and geographic coordinates (n = 9089). We modelled the prevalence of stunting and its determinants using Bayesian geospatially explicit regression models. The prevalence of stunting among children under five years was 36.3% (95% credible interval (CrI); 22.6%, 51.4%) in Ethiopia, with wide variations sub-nationally and by age group. The prevalence of childhood stunting ranged from 56.6% (37.4–74.6%) in the Mekelle Special zone of the Tigray region to 25.5% (10.5–48.9%) in the Sheka zone of the Southern Nations, Nationalities and Peoples region. Factors associated with a reduced likelihood of stunting in Ethiopia included non-receipt of breastmilk, mother’s BMI (overweight/obese), employment status (employed), and higher household wealth, while the enablers were residence in the “arid” geographic areas, small birth size of the child, and mother’s BMI (underweight). The prevalence and determinants of stunting varied across Ethiopia. Efforts to reduce the burden of childhood stunting should consider geographical heterogeneity and modifiable risk factors.