Purpose: We studied whether physical activity (PA) counseling for parents influenced the level of parental support of children’s PA and leisure-time PA in children of different levels of initial parental support. We hypothesized that the initial level of parental support would moderate the intervention efficacy. Method: Children (n = 44, Mage = 6.09 ± 1.17 years) and their parents (n = 61) randomly assigned to an intervention group received counseling for 6 months. Children in the control group (n = 47, Mage = 6.12 ± 1.11 years) and their parents (n = 63) did not receive any counseling. Parental support was assessed using the Family Physical Activity Environment Questionnaire, and children’s leisure-time PA was recorded using triaxial accelerometers at baseline, at 6 months, and at 12 months. The efficacy of the intervention was tested by linear mixed-effects modeling adjusted for confounding variables (Model 1) and additionally for children’s participation in organized PA or sports (Model 2). Results: Parents within the lowest initial parental support intervention tertile significantly increased their support, and their children’s mean level of leisure-time PA significantly improved compared with the corresponding controls during the counseling period. On the other hand, intervention was found to have an unfavorable influence especially in the PA of children of initially highly supportive parents. Conclusion: Targeting PA counseling for parents with low support of their children’s PA could contribute to better family-based PA counseling efficacy.