Background: Poor complementary feeding of children aged 6–23 months contributes to the characteristics negative growth trends and deaths observed in developing countries. Evidences have shown that promotion of appropriate complementary feeding practices reduces the incidence of stunting and leads to better health and growth outcome. This study was aimed at assessing practices of complementary feeding and associated factors among mothers of children aged 6–23 months. Methods: A community-based cross sectional study design was conducted among 603 mothers who had children with 6–23 months of age in the six randomly selected Kebeles (smallest administrative unit). A multistage sampling technique was used to identify study subjects. Data was collected using pre-tested structured questionnaire. Data was entered in to Epi info version 3.5.1. Data cleaning and analysis were done using SPSS version 20. Odds ratios (ORs) with 95 % confidence interval (CI) were computed to measure the strength of association. Results: The practices of timely initiation of complementary feeding, minimum meal frequency and minimum dietary diversity were 72.5, 81.5 and 59.2 % among mothers of 6–23 months aged children, respectively. The practice of appropriate complementary feeding was 36.2 %. Decision making with husband only on how the money be used [AOR: 0.434 (95 % CI: 0.20-0.94], Health Facility delivery [AOR: 2.19 (95 % CI: 1.47, 3.26], Urban place of residence [AOR: 1.513 (95 % CI: 1.02, 2.39)], Having mass media exposure [AOR: 1.55 (95 % CI: 1.02, 2.27)] were found to be independent predictors of appropriate complementary feeding practice of 6–23 months old children. Conclusion: Appropriate complementary feeding of mothers with children aged 6–23 months was low. Mothers who are illiterate, living in rural community and do not have media exposure, home delivery and husband decision making were associated factors for inappropriate feeding practices. Therefore, women empowerment and nutrition counseling on child feeding practices were recommended.