Establishment in urbanized environments is associated with changes in physiology, behaviour, and problem-solving. We compared the speed of learning in urban and rural female common mynas, Acridotheres tristis, using a standard visual discrimination task followed by a reversal learning phase. We also examined how quickly each bird progressed through different stages of learning, including sampling and acquisition within both initial and reversal learning, and persistence following reversal. Based on their reliance on very different food resources, we expected urban mynas to learn and reversal learn more quickly but to sample new contingencies for proportionately longer before learning them. When quantified from first presentation to criterion achievement, urban mynas took more 20-trial blocks to learn the initial discrimination, as well as the reversed contingency, than rural mynas. More detailed analyses at the level of stage revealed that this was because urban mynas explored the novel cue-outcome contingencies for longer, and despite transitioning faster through subsequent acquisition, remained overall slower than rural females. Our findings draw attention to fine adjustments in learning strategies in response to urbanization and caution against interpreting the speed to learn a task as a reflection of cognitive ability.