Boje's international career began in 1995 against Zimbabwe, and although he was in and out of the team due to injuries he established himself as South Africa's first choice spin bowler. Due to the amount of all-rounders in the South African team, Boje usually batted at eight or nine in the batting order, despite a first classbatting average of 32 and both Test and ODI averages around 26, which was the highest for a regular number nine in Test cricket in the 2000s. However, despite the reasonably high average he never hit a Test century, although did make two ODI centuries against New Zealand in 2000–01.
In December 2006, Boje announced his retirement from international cricket, effective immediately. He finished his career with exactly 100 Test wickets, the wicket of Mahela Jayawardene in his final Test brought up his milestone.