Background: Malnutrition has been responsible for the death of millions of under five children annually. Majority of these deaths are often associated with inappropriate feeding practices and occur during the first year of life. In developing countries complementary feeding frequently begins too early or too late, and foods are often nutritionally inadequate and unsafe. Objectives: The purpose of this study was to assess magnitude and factors associated with appropriate complementary feeding practice among mothers with children age 6– 23 monthsat health centers in Kolfe Keranio Sub City, Addis Ababa. Methods: Institutional based cross sectional study design was conducted among 243 mothers who had children age 6–23 months in three selected health centers .Data were collected using pre-tested, pre-coded and interviewer-administered questionnaires from March 13-April 7, 2017. Data were cleaned with Epi InfoTM 7 version and analysis was done by using SPSS version 20. OR with 95% confidence interval was computed to measure the strength of association between the dependent and independent variables. Result: The practice of timely initiation of complementary feeding, minimum dietary diversity and minimum meal frequency were 85.2%, and 27.6% and 85.2% respectively. Among the respondents 21.8% had practiced the minimum acceptable diet. The overall prevalence of appropriate complementary feeding practice in the study area was 18.5%. Multivariable logistic regression showed that lower age of children [AOR=.131:95%CI: (.053 .327)], combination feeding i.e. spoon, hand and bottle feedings [AOR=3.535 95%CI: (1.013 12.339)], child who fed thin gruel [AOR= .090 95%CI: (.014 .561)] were negatively associated with appropriate complementary feed g practice. Conclusion: The prevalence of appropriate complementary feeding of children aged 6-23 months was low. Age of the child, method of feeding, and texture of complementary food were factors that affect appropriate complementary feeding practice.