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.)
In Round 10, 2005, he had the embarrassing honour of being the fullback playing on Gehrig in what was the St Kilda forward's 200th game, where he kicked eight goals in the match playing on Barry. In Round 1, 2006, he was the fullback playing on Essendon full-forward Matthew Lloyd in what was the latter's first game as Essendon captain; Barry had six of Lloyd's eight goals kicked against him.
Barry will always be remembered as the player who "caught the cup" for the Swans. Not only did he ensure the victory for the Swans but Barry's backline heroics were instrumental to the Swans' success which culminated with one of Barry's trademark spectacular marks during the 2005AFL Grand Final between Sydney and West Coast. After a kick from Dean Cox was sent into the forward line, Barry marked in a big pack within the dying seconds of the game to secure the Swans' long-awaited premiership. Commentator Stephen Quartermain described the mark, as:
"Cox throws it onto the left, one last roll of the dice for the Eagles! Leo Barry you star!..(siren in background)..The longest premiership drought in football history is over! For the first time in 72 years the Swans are the champions of the AFL!"
This image was later used by Tabcorp for promotional purposes, with Barry claiming that the image was "worth A$50,000", despite other players being featured in the photo.