On 10 June 2008, he signed with AEK Athens on a four-year contract. He wore the number 24 shirt.
Burns made his Greek Super League debut for AEK Athens on 28 February 2009, as 65th-minute substitute against Skoda Xanthi at the Spyros Louis Olympic Stadium in Athens. Burns scored the winner against Rangers in the final game of the 2010 Sydney Festival of Football. He scored his first league goal on 27 February 2011, in a 3–2 away win against Ergotelis.
On 25 June 2014 it was announced that he had signed a 2-year deal to join New Zealand team the Wellington Phoenix in the Hyundai A League beginning with the 2014/15 season. On 18 October 2014, he scored his debut goal for the club against the Central Coast Mariners. Burns made history in the Round 8 clash against Melbourne City, becoming the first Phoenix player to score a hat trick in their 5-1 victory. On 6 December he scored his 8th goal of the season in a 3-1 come from behind victory over the Newcastle Jets at Hunter Stadium. On 21 December he scored two goals in a 2-0 away win over Sydney FC, making him the fastest A-league player to ever reach 10 goals in a season, and did not return to New Zealand as he got his for international recall for Australia ahead of Asian Cup.
He made his debut for the Socceroos with a brief appearance in the 3–0 win over Singapore on 30 June 2007.
Burns came on as a substitute in the opening game in Melbourne of the 2015 AFC Asian Cup against Kuwait, and was twice denied a goal, the first when his shot hit the crossbar, and the second when the goalkeeper made a brilliant save.
On 17 January 2015, Burns made his first start for the Socceroos since 2011, when he lined up for the final group game of the 2015 AFC Asian Cup for Australia against South Korea.