Originally from Deniliquin, New South Wales, Barry attended St Ignatius' College, Riverview before being drafted as a zone selection in the 1994 National Draft and making his debut in the final round of the 1995 season against Collingwood. For the next few seasons he played in the forward line without consistency, struggling to find a place in an already strong forward line. He did, however, display an ability to take spectacular jumping marks, earning him the nickname "Leaping Leo".
In 2001, Swans coach Rodney Eade moved Barry to the backline, where he prospered. Despite being short for a fullback at 184 cm, he has successfully played on much taller opponents, making use of his leaping skills and using his body well. Regularly playing on opponents 10–15 cm taller than he is, Barry rarely has multiple goals kicked upon him. Barry's unique defensive ability is observed in 2004 when Barry kept 196 cm St Kilda full forward Fraser Gehrig to two handballs for the whole game (for this effort, he received three Brownlow Medal votes).
Despite being only 184 cm tall, Barry is surprisingly strong which has become a useful necessity for him when facing taller opponents such as Fraser Gehrig, Brendan Fevola, David Neitz, Anthony Rocca, Chris Tarrant, Quentin Lynch, Matthew Lloyd, Jonathan Brown, Daniel Bradshaw and Matthew Richardson, amongst others.
Barry has twice been included in the All-Australian team, in 2004 and 2005.
On 18 August 2009, Barry announced he would retire from football at the end of the current season.