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 squad. By winning the first Test, Bangladesh secured their first win against the West Indies, their first overseas Test victory, and only their second Test win. The West Indies side was very inexperienced due to the fallout of a dispute between the West Indies Cricket Board and the West Indies Players' Association over pay. The first XI had made themselves unavailable for selection and a new squad had to be chosen. Seven West Indies players made their Test debut in the match and the side was captained by Floyd Reifer who had played the last of his four Tests ten years earlier. Hossain was fined 5% of his match fee for excessive appealing, one of three Bangladesh players reprimanded after the match for the same reason. Bangladesh went on to win the second Test, and in the process secured their first overseas series win. Having played in both Tests, Hossain took three wickets at an average of 42.66.
The next time Shahadat played was when Bangladesh hosting India for two Tests in January 2010. In the lead up to the first match Indian batsman Virender Sehwag called the Bangladesh bowling attack ordinary, provoking anger amongst the team. India were dismissed for 234 in the first innings, with Shahdat taking 5/71. It was the third time he had taken a five-wicket haul in a Test innings. Captain Shakib Al Hasan remarked that "[Shahadat] didn't bowl all that well; he can bowl much better than this. But it's good for his confidence that he got wickets, as he is on a comeback." Bangladesh were unable to build on their early success and went on to lose the series 2–0. Shahadat was his team's second-highest wicket-taker across the two Tests, but after taking a five-wicket haul in the first innings of the series he managed just two more. Between October 2008 and March 2010, Shahadat endured a lean spell in which he took 18 Test wickets at an average of 67.50. His bowling average in this period was amongst the worst for the 20 innings before a bowler took a five-wicket haul in Tests.
Bangladesh toured England in May 2010 for two Tests and three ODIs. Hossain played in the first Test at Lord's and was one of three Bangladesh players still in the team five years after the team's first tour of England. Contrasting with his debut effort, Shahadat took five wickets for 98 runs and in the process became the first Bangladeshi cricket to be added to the Lord's honours board. England won the series 2–0 and Hossain took a single wicket in the second Test. He finished as his team's second highest wicket-taker with six wickets in the series. Hossain was part of the 13-man Bangladesh squad that played in the 2010 Asian Games in late November. They played Afghanistan in the final and won by five wickets, securing the country's first gold medal at the Asian Games.
Dhaka Division won the One-Day National Cricket League in November 2010, with all the matches held in the space of three weeks. Hossain took ten wickets from six matches in the tournament, producing his best figures of 4/39 in the final against Barisal Division to help his team to victory. Hossain was not included in Bangladesh's 15-man squad for the 2011 World Cup, having lost his place in the ODI side to younger fast bowlers Shafiul Islam and Rubel Hossain. A broken toe, sustained during a game of beach football, prevented him from taking part in Bangladesh's tour of Zimbabwe in July and August 2011, a series which marked Zimbabwe's return to Test cricket and Bangladesh's first Test match since the tour of England over 14 months earlier. National captain Shakib Al Hasan lamented Hossain's absence, saying "I think [Shahadat Hossain] Rajib is a huge loss. He's been our best Test bowler for quite a while." He returned to action in the Bangladesh Cricket Board Cup in September, taking six wickets in four games for Bangladesh A against a team of academy players and the full national side. Hossain was recalled to the Test squad in October to face the West Indies in a two-match series. He also played in both of Bangladesh's Tests against Pakistan in December. During the second Test against Pakistan, Hossain bowled several no-balls. In the first four Tests of his comeback Hossain took just two wickets whilst conceding 394 runs.
The Bangladesh Cricket Board founded the six-team Bangladesh Premier League in 2012, a twenty20 tournament to be held in February that year. An auction was held for teams to buy players, and Hossain was bought by the Khulna Royal Bengals for $30,000. When Bangladesh hosted the 2012 Asia Cup Hossain was included in the squad and played his first ODI since February 2010. He conceded the more runs than any other bowler in the tournament and his four wickets cost on average 62.00 runs each; when the BCB announced its central contracts in April Hossain's was not renewed.
Noted for his height and aggression, Hossain was cited as the fastest bowler in the Bangladesh team by former coach Dav Whatmore in 2005. By 2010 his bowling rarely exceeded 80 miles per hour (130 km/h). His run-up is smooth, his deliveries come in at an angle and bowls with pace. He has become renowned for hurting batsmen with his bouncer, having hit international players such as Mathew Sinclair and Ricky Ponting over the course of his career. His bowling has come in for criticism from fellow bowler Mashrafe Mortaza for conceding too many runs. He has said his idols include Wasim Akram, Shoaib Akhtar, Steve Harmison and Brett Lee (all fellow fast bowlers).
On Sunday 13 September 2015 Hossain and his wife were accused of "torture and abuse" of an 11-year-old maid. The chief executive of the BCB, Nizamuddin Chowdhury, says Hossain has been suspended “from all kind of cricketing activities under BCB’s jurisdiction until a final decision is reached regarding the ‘torture accusations’ brought against him. On 5 October 2015 he surrendered before a court in Dhaka, was sent to prison, and charged with child repression and employing a minor. In December 2015 he was granted bail until 31 March 2016.
On 29 December 2015, Hossain and his wife were formally charged with torture and it was announced that the case will be heard on 12 January.