Each region except the first and last contains two missions with one of either a crystal unlocking the next region or two upgrades for your prince as a reward. The upgrade missions are always marked by a mine shaft icon on the map. Completing any of these missions will unlock the achievement. The first available such mission is "The Northern Pass" in the second region (after the tutorial missions)