Op 21 juni 2003 maakte Brines zijn debuut in Europees verband tijdens een wedstrijd tussen OFK Beograd en Trans Narva in de UEFA Intertoto Cup; het eindigde in 6–1 voor Beograd en de Schotse scheidsrechter gaf vijf gele kaarten.[1] Zijn eerste interland floot hij op 18 augustus 2004, toen Ierland met 1–1 gelijkspeelde tegen Bulgarije. Tijdens dit duel gaf Brines geen gele kaarten.[2]