Born in Narayanganj, Hossain began playing cricket during his teenage years in his home town, and his father, a banker, agreed to send him to a training camp. Whilst at the training camp he was spotted by a scout and was referred to the Bangladesh Institute of Sports to improve.

Hossain soon found himself called up for the Bangladesh U-19 cricket team for the 2003–04 Asian U-19 Tournament in Pakistan, but he didn't find much success, taking only 2 wickets in 3 appearances, as Bangladesh lost all their group stage matches and failed to progress to the final. His run in the team continued, however, as he was picked for the 2004 U-19 Cricket World Cup as Bangladesh played hosts. In the group stage he played in all 3 matches, taking 5 wickets, as the team progressed to the Plate competition of the Cup. For the Plate final, he took a wicket as Bangladesh defeated Australia to finish ninth out of sixteen. He finished with six wickets at an average of 28.50, and was named by Cricinfo writer Rabeed Imam as the fastest bowler and one of the most promising players in the tournament.

In his debut Test against England at Lord's in 2005 Hossain conceded 101 runs in 12 overs without taking a wicket, an economy rate of 8.41.

On the tour to Zimbabwe in July 2006, Hossain became the first Bangladeshi to take a hat-trick in One Day Internationals.

South Africa toured Bangladesh in February 2008 for two Tests and three ODIs. Though they were expected to win with ease, South Africa were made to work hard for victory in the opening Test. Cricinfo recorded that Hossain "bowled at a lively pace and with tremendous control" to help Bangladesh gain a first-innings lead. He claimed career-best figures of 6/27, and despite a further three in the second innings South Africa won by five wickets. Bangladesh lost the second match by an innings and 205 runs with Hossain taking 3/107. In January 2009 Shahadat was dropped from the national side. Chief selector Rafiqul Alam stated that Shahadat was too expensive, having conceded runs at 6.63 an over in 18 ODIs in 2008, and believed he would benefit from returning to domestic cricket.

When July–August 2009, Bangladesh toured the West Indies, Hossain was included in the 15-man