In the 2008/09 Bangladeshi domestic season Mahmudullah finished as the second-highest run-scorer in the competition with 710 runs at an average of 54.61 and was subsequently recalled to the ODI squad to face Zimbabwe in three ODIs and a tri-series with Sri Lanka and Zimbabwe. Mahmudullah made his Test debut on 9 July 2009 against the West Indies. He performed poorly with the bat, but obtained the best test bowling figures in a match by a Bangladeshi on debut, with an eight-wicket haul, including a five wicket haul in the second innings. This played a major role in Bangladesh's second Test win, and the first on foreign soil. He is now a regular member in the squad.
Although Mahmudullah scored a Test century batting at number 8 against New Zealand, the selection committee preferred not to promote him up the order due to a perceived weakness against fast bowling, despite the number four spot having no permanent occupant. He was included in Bangladesh's 15-man squad for the 2011 World Cup. On 20 September, Mahmudullah was named Bangladesh's vice-captain, taking over from Tamim Iqbal after the previous captain and deputy were sacked. When West Indies toured in October, Mahmudullah missed all the fixtures with a viral fever. He recovered in time to rejoin the squad to face Pakistan in three ODIs in November. Mahmudullah scored 56 runs and bowled in just one match, taking three wicket from seven deliveries.