Suboptimal healthcare quality may be a barrier to achieving child health improvements, yet little is known about the relationship between provider compliance with evidence-based practices and client behavior change. We assess provider compliance in the context of infant and young child feeding (IYCF) counseling, its relationship with client IYCF behaviors in Bangladesh, and explore its potential determinants. We use data from a 2017 evaluation of an IYCF program that includes a health worker survey (n = 74), caregiver survey (n = 232), and direct service observation checklists of counseling sessions (n = 232 observations of 74 health workers). We assess the relationship between provider compliance with recommended IYCF counseling topics and behaviors (standardized to a 100-point scale) and three reported IYCF behaviors among clients using multi-level models with random effects at the health worker and sub-district (sampling) levels. We also evaluate whether health worker self-efficacy, satisfaction, and technical knowledge are associated with provider compliance. Health worker compliance was significantly associated with reported exclusive breastfeeding for children under 6 months of age (adjusted odds ratio per 1 percentage point increase in counseling compliance score = 1.06, 95% CI 1.01, 1.12) and marginally associated with minimum dietary diversity (adjusted odds ratio per 1 percentage point increase in counseling compliance score = 1.05, 95% CI 1.00, 1.11). Counseling compliance was significantly and positively associated with both health worker self-efficacy and technical knowledge. We find evidence for an association between health worker compliance and client health behaviors; however, small effect sizes suggest that behavior change is multifactorial and affected by factors beyond care quality. Improvements to technical quality of care may contribute to desired health outcomes; but policies and programs seeking to change health behaviors through counseling may also wish to target upstream factors such as self-efficacy, alongside technical skill-building and knowledge, for maximum impact.