Complementary feeding is one of the top measures in Nigeria to reduce malnutrition. However, there is consistent evidence of poor practice in Nigeria. This study aims to evaluate how nursing mothers in Nigeria perceive complementary feeding and understand how their perceptions influence their complementary feeding practices. The study involved four sessions of Focus Group Discussions with a total of 31 participants. The findings revealed that mothers introduced complementary feeding early because they believed that breast milk alone was insufficient before the age of 6 months. Some mothers also perceived that non-infant cereals and milk were better than their infant counterparts, claiming that they aid weight gain. Additionally, some healthy foods were avoided due to myths, and local herbs, commonly known as agbo, were given to some children. To ensure that the World Health Organization guidelines on complementary feeding are accepted in Nigeria, policymakers need to target all those involved in caregiving for the child in the Nigerian setting. This includes health workers, mothers, fathers, and grandmothers.