Background In efforts to reduce neonatal mortality, the World Health Organization (WHO) has included breastfeeding among its recommended packages of interventions. Early initiation of breastfeeding and avoidance of prelacteal feeding are key contributors to optimal feeding practices. This study aims to assess the prevalence and associated factors of early breastfeeding practices in Sudan. Methods This study utilises the cross-sectional nationally-representative Sudan Multiple Indicator Cluster Survey (MICS) conducted in 2014. The sample includes women who had a live birth in the two years before the survey and their self-report on early breastfeeding practices, namely early initiation and prelacteal feeding. Percentages of these early breastfeeding practices indicators were estimated accounting for the complex survey design. Multivariable logistic regression analyses were used to examine the factors associated with these outcomes. Results Of 5622 mothers, 69% initiated breastfeeding within one hour of birth, 72% avoided prelacteal feeding in the first three days after birth, and 51% met the criteria for both (i.e. practised optimal early feeding practice). Optimal early feeding varied across regions of Sudan. Birth by caesarean section (Adjusted Odds Ratio [AOR] 0.34; 95% CI 0.25, 0.47) and at a health facility (AOR 0.75; 95% CI 0.60, 0.94) were negatively associated with optimal early feeding practice. Mothers with secondary education (AOR 1.62; 95% CI 1.30, 2.02), those who desired their pregnancy at the time (AOR 1.31; 95% CI 1.08, 1.60), those who were assisted by a skilled birth attendant at birth (AOR 1.48; 95% CI 1.19, 1.83), and those who gave birth to female infants (AOR 1.16; 95% CI 1.02, 1.33) had higher odds of use optimal early feeding practice. Similarly, the odds of optimal early feeding increased with parity and maternal age. Conclusions Only half of Sudanese mothers practised optimal early feeding practice, with important differences between regions in the country. Early feeding practices in Sudan are associated with various maternal, child and community level factors. The findings suggest the need to develop breastfeeding promotion programs with consideration of regional variations and healthcare system interventions.