He was a stalwart of the Wales Under 21 Grand Slam victory in 2005. In May 2008 he was selected for the Wales' squad for the 2008 Tour of South Africa, making his debut as a substitute in the 2nd test on 14 June. Wales lost 37–21. He kept his place in the squad throughout the 2008–09 season and on 14 November, he made his first start against Canada. Wales won 34–13. He came on as a replacement in the 18th minute for Jamie Roberts in the match against the Wallabies. Critics thought this would affect Wales but Bishop held his own as Wales won 21–18, the only win that for Northern Hemisphere against one of The Big Three. Bishop then came on as a subsititute against Scotland in the Six Nations. He it was his only game time in the tournament, although he was an unused replacement against England. Bishop then started for Wales on their North America tour opener against Canada. The Welsh team were missing players due to the Lions tour and injuries but still won 32–23. Bishop then started against United States. Wales won 48–15.
On 18 January 2010 he was named in the 35 man Wales national Squad for the 2010 Six Nations tournament. He was on the bench for every game, only coming on against Ireland.