Having played only three first-class matches, he was called up to the squad for the third Test against South Africa in March 2001, but did not make his Test debut until January 2004, again against South Africa. After one further Test against England he lost the spinner's position to Omari Banks.
Following a productive domestic season in 2006, Mohammed was recalled firstly to the ODI side, and subsequently to the Test side, for the series against India. A match-winning performance in the final ODI was followed by a half century in the first Test at Antigua, which led to the West Indies hanging on for a draw with one wicket remaining. He played in a subsequent series against Pakistan, where he impressed with his lower-order batting.