League Cup Final at a left back position against Dunfermline Athletic, due to Wilson being cup-tied and Celtic won 3–0. He later made two appearances later in the 2005–06 season and despite being dropped from the first team, his contributions saw the club win the league. At the end of the 2005–06 season, Wallace went on to make fourteen appearances in all competitions. Ahead of the 2006–07 season, Wallace went on trial at Championship side Birmingham City. It came after when he performed a poor display in Celtic's pre–season tour. Amid to his future at the club, Wallace made two more appearances for Celtic, both starting the matches at the start of the 2006–07 season. However, he was clearly no longer part of the plans of the Celtic management and was expected to leave the club. Sunderland Wallace was sold to Sunderland on 31 August 2006 in a deal including teammate Stanislav Varga for a combined fee of up to £1,100,000. Upon joining the club, he said about his former teammate turned manager Roy Keane: "I've been on the wrong end of a Roy Keane rollicking once or twice and I still decided to come here. But to be fair, if he does say something, it's going to be good for you. He wants to help you. When he does do it, it's positive criticism. He demands the best because he was world class for a decade. Obviously, he demands the best from everyone here to take the club back up." Wallace made his Sunderland debut against Derby County on 9 September 2006 and scored the winner in a 2–1 win. This was followed up by setting up a goal for Liam Miller, who scored 14 yards past the goalkeeper, in a 3–0 win against Leeds United four days later on 13 September 2006. However in a match against Ipswich Town on 23 September 2006, he played a role that led Jason de Vos to score an own goal, but was sent–off in the 86th minute for a second bookable offence, in a 3–1 loss. After serving a one match suspension, Wallace returned to the first team, coming on as a 52nd-minute substitute, in a 4–1 loss against Preston North End on 14 October 2006. In a match against Hull City on 28 October 2006, he scored his second goal for the club, which turns out to be the winning