Although worked-out examples play a key role in cognitive skill acquisition, research demonstrates that students have various levels of meta-cognitive abilities for using examples effectively. The Example Analogy (EA)-Coach is an Intelligent Tutoring System that provides adaptive support to foster meta-cognitive behaviors relevant to a specific type of example-based learning known as analogical problem solving (APS), i.e., using examples to aid problem solving. To encourage the target meta-cognitive behaviors, the EA-Coach provides multiple levels of scaffolding, including an innovative example-selection mechanism that chooses examples with the best potential to trigger learning and enable problem solving for a given student. To find such examples, the mechanism relies on our novel classification of problem/ example differences and associated hypotheses regarding their impact on the APS process. Here, we focus on describing (1) how the overall design of the EA-Coach in general, and the example-selection mechanism in particular, evolved from cognitive science research on APS; (2) our pilot evaluations and the controlled laboratory study we conducted to validate the tutor’s pedagogical utility. Our results show that the EA-Coach fosters meta-cognitive behaviors needed for effective learning during APS, while helping students achieve problem-solving success.