Background: Health literacy (HL) and nutrition literacy (NL) are important issues to consider, in the provision of health care to children and the establishment of healthy eating behaviors. Aim: The study investigates the possible role of HL and NL levels of Greek parents, in parental Feeding Practices (PFP). Methods: This is a cross-sectional study which was conducted in the urban area of the Attica region, Greece. The sample consisted of 402 parents (68.4% mothers). Parents completed the Greek version of Comprehensive Parental Feeding Questionnaire, the European Health Literacy Questionnaire 47 and the Greek version of the Nutrition Literacy Scale. Sociodemographic and anthropometric characteristics were also assessed. The non-parametric tests Mann-Whitney and Kruskal Wallis, the chi-square test and linear regression models were applied. Results: The median for HL and NL were 33.69 and 24.00, respectively. Mothers applied the “child control” practice more frequently than fathers ( p = 0.015). Linear regression analysis revealed that HL was associated positively with “healthy eating guidance” and “monitoring” ( p = 0.009 and p < 0.0001, respectively) and negatively with “emotion regulation/food as reward” and “child control” ( p = 0.037 and p = 0.015, respectively). NL was associated positively only with “healthy eating guidance” ( p = 0.009), positively but marginally with “monitoring” ( p = 0.051) and negatively with “emotion regulation/food as reward” ( p = 0.020). Conclusions: Higher parental levels of HL and NL are significantly positively associated with better parental feeding practices in Greece.