Robinson kwam in totaal 52 keer (één doelpunt) uit voor de nationale ploeg van Wales in de periode 1999–2009. Hij maakte zijn debuut op zaterdag 4 september1999 in de EK-kwalificatiewedstrijd tegen Wit-Rusland, die met 2-1 werd gewonnen dankzij treffers van Dean Saunders en Ryan Giggs. Robinson viel in dat duel – het eerste onder leiding van bondscoach Mark Hughes – na 81 minuten in voor Mark Pembridge.