Introducing appropriate complementary feeding at 6 months of age is crucial for the optimal growth and development of an infant. In Ethiopia, however, no previous national-level studies have examined the trends and associated factors of complementary feeding practices. The aim of this study is to investigate the trends and determinants of complementary feeding practices in Ethiopia from 2005 to 2016. The study was conducted using the Ethiopia Demographic and Health Survey (EDHS) data for 2005 (N = 2,520), 2011 (N = 2,850), and 2016 (N = 2,864). Percentage point changes in complementary feeding indicators were estimated to examine the trends over the EDHS years. Multivariate logistic regression was used to examine the association between socioeconomic, demographic, health service, and community-level factors and (a) the introduction of complementary foods, (b) minimum dietary diversity (MDD), (c) minimum meal frequency (MMF), and (d) minimum acceptable diet (MAD). The proportion of mothers who met MDD increased from 6.3% to 13.5% (p < .001), and MAD increased from 4.1% to 7.1% (p = .003) from 2005 to 2016. Improvements in the introduction of complementary foods (from 50.3% to 59.5%, p = .051) and MMF (from 41.3% to 43.6%, p = .288) were not statistically significant. Maternal education and occupation were associated with the introduction of complementary foods, MDD, MMF, and MAD. Higher partner education and frequent antenatal visits were associated with MDD and MAD. Children whose mothers listened to the radio had higher odds of MDD, MMF, and MAD. Our analysis of the EDHS suggests that the proportion of MDD and MAD were unacceptably low. Interventions aiming to improve complementary feeding practices in Ethiopia should also target mothers with low education, antenatal service usage, and media exposure.