Wallace was een verdediger en speelde zijn eerste interland op 27 september1995 tegen Jamaica. Hij maakte deel uit van de selectie voor het WK voetbal 2002 en het WK voetbal 2006. Hij speelde in totaal exact honderd interlands in de periode 1995-2009, waarin hij driemaal tot scoren kwam.