When learning a new concept, should students engage in problem solving followed by instruction (PS-I) or instruction followed by problem solving (I-PS)? Noting that there is a passionate debate about the design of initial learning, we report evidence from a meta-analysis of 53 studies with 166 comparisons that compared PS-I with I-PS design. Our results showed a significant, moderate effect in favor of PS-I (Hedge’s g 0.36 [95% confidence interval 0.20; 0.51]). The effects were even stronger (Hedge’s g ranging between 0.37 and 0.58) when PS-I was implemented with high fidelity to the principles of Productive Failure (PF), a subset variant of PS-I design. Students’ grade level, intervention time span, and its (quasi-)experimental nature contributed to the efficacy of PS-I over I-PS designs. Contrasting trends were, however, observed for younger age learners (second to fifth graders) and for the learning of domain-general skills, for which effect sizes favored I-PS. Overall, an estimation of true effect sizes after accounting for publication bias suggested a strong effect size favoring PS-I (Hedge’s g 0.87).