Mahmudullah was called up for Bangladesh's ODI squad for the 3 matches against Sri Lanka in Bangladesh's tour of the country in July 2007. He made his debut on the tour, in the third ODI, where he was Bangladesh's second highest scorer (with 36) and also took 2 wickets, in a match Sri Lanka won by 39 runs. He went on to be picked for Bangladesh's squads for a Quadrangular Series in Kenya in 2007 and the 2007 Twenty20 World Championship.
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.
On 9 March 2015, in the 2015 ICC Cricket World Cup, against England, he scored the first century by a Bangladeshi batsman in World Cup history. Bangladesh went on to win the match and went through to the quarter finals. In the next match, on 13 March, he scored another World Cup century, this time against New Zealand, although New Zealand won by 3 wickets. In six matches in the World Cup he scored 365 runs at an average of 73.00.